CF1268B - Domino for Young

Main idea: give you a row of non increasing matrix with height from left to right, input n(1 ≤ n ≤ 300000), representing n columns of rectangles; the next row has n numbers, representing the corresponding matrix height (1 ≤ ai ≤ 300000,ai ≥ ai+1). Ask how many matrices you can insert into 12 or 21.

Solution: greedily consider each column. If it is even, fill 1 * 2 directly. If it is odd, record the current column. When we draw a picture, if there are two columns with odd height closest to each other, and there are even matrices with even height in the middle, it can be eliminated (drawing is obvious). If there are only an odd number of matrices with even height between them, then it can't be eliminated, and at least two points will remain, that is, the bottom two points of the matrix with odd height (for greedy consideration, it's better to keep the bottom than the top). Just keep greedy according to this idea.

Generation code

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main(int argc, char const *argv[])
{
	ll ans = 0 ;
	int n ;
	stack<int> st ;
	while(!st.empty()) st.pop() ;
	scanf("%d",&n) ;
	for(int i = 1, x ; i <= n ; ++ i)
	{
		scanf("%d",&x) ;
		ans += x / 2 ;
		if(x % 2 == 1)
		{
			int tmp = i % 2 ;
			if(!st.size() || st.top() == tmp) st.push(tmp) ;
			else st.pop(), ans ++ ;
		}
	}
	printf("%lld\n",ans) ;
	return 0;
}

POJ 2528 Mayor's posters
Main idea: post the posters in order. The posters will cover the posters behind it. How many posters can you see at last.
Solution: the given length may be very large, there is 1e9, without processing, directly maintaining a line tree will definitely
MLE,TLE, but we notice that there are only 2e4 points in total, so we can use the idea of discretization to preprocess the interval first
Discretization: only the mutual relations among elements are considered, for example, 1.10 million million, which can be mapped to 1.23 3

Stuck point: it is not simply to separate the boundary of an interval into points, but to add another point between two adjacent points with a difference greater than 1 after de duplication
For example [1,20] [1,10] [15,20]
After discretization, interval 1 covers 1, 4; interval 2 covers 1, 2; interval 3 covers 3, 4
However, the specific examples are not completely covered, and the above methods can solve this problem.

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <string>
#include <cstring>
using namespace std;
const int maxn = 1e4 + 10 ;
int n ;
int vis[maxn<<3],sum[maxn<<4] ;
int li[maxn<<1],ri[maxn<<1],lsh[maxn<<2] ;
void pushdown(int rt)
{
	sum[rt<<1] = sum[rt] ;
	sum[rt<<1|1] = sum[rt] ;
	sum[rt] = -1 ;
}
void update(int L, int R, int C, int l, int r, int rt)
{
	if(L <= l && r <= R)
	{
		sum[rt] = C ;
		return ;
	}
	if(sum[rt] != -1) pushdown(rt) ;
	int mid = (r + l) / 2 ;
	if(mid >= R) update(L,R,C,l,mid,rt<<1) ;
	else if(L > mid) update(L,R,C,mid+1,r,rt<<1|1) ;
	else update(L,mid,C,l,mid,rt<<1),update(mid+1,R,C,mid+1,r,rt<<1|1) ;
}
int ans ;
void query(int l, int r, int rt)
{
	if(!vis[sum[rt]] && sum[rt] != -1)
	{
		ans ++ ;
		vis[sum[rt]] = 1 ;
		return ;
	}
	if(l == r) return ;
	if(sum[rt] != -1) pushdown(rt) ;
	int mid = (l + r) / 2 ;
	query(l,mid,rt<<1) ;
	query(mid+1,r,rt<<1|1) ;
}
int main(int argc, char const *argv[])
{
	int t ;
	scanf("%d",&t) ;
	while(t --)
	{
		scanf("%d",&n) ;
		memset(sum,-1,sizeof sum) ;
		memset(vis,0,sizeof vis) ;
		int tot = 0 ;
		for(int i = 0 ; i < n ; ++ i)
		{
			scanf("%d %d",&li[i],&ri[i]) ;
			lsh[tot ++] = li[i] ;
			lsh[tot ++] = ri[i] ;
		}
		sort(lsh,lsh+tot) ;
		int tot = unique(lsh,lsh+tot) - lsh ;
		int tmp = tot ;
		for(int i = 1 ; i < tmp ; ++ i)
		{
			if(lsh[i] - lsh[i-1] > 1) lsh[tot ++] = lsh[i - 1] + 1 ;
		}
		sort(lsh,lsh+tot) ;
		for(int i = 0 ; i < n ; ++ i)
		{
			int x = lower_bound(lsh,lsh+tot,li[i]) - lsh ;
			int y = lower_bound(lsh,lsh+tot,ri[i]) - lsh ;
			update(x,y,i,0,tot-1,1) ;
		}
		ans = 0 ;
		query(0,tot-1,1) ;
		printf("%d\n",ans) ;
	}
	return 0;
}