2018 joint examination of nine provinces & Merging of line segment trees

A pair of wooden chess

According to the title , A grid can be placed if and only if there are no chess pieces in this grid and there are chess pieces in all grids on the left and above this grid .

It can be seen that the number of pieces in each line is monotonous

At most 10 That's ok , The total number of cases is equivalent to 0~10 this 11 Select ten numbers that can be repeated

The number of repeatable sets , It's equivalent to just    A legal arrangement of chess pieces

The difference between the first one and the second one is required to be the largest , So in the first person's round , Save the maximum value of the difference , The second man's turn , Save the minimum value of the difference

use unordered_map Press a decimal number , Save the usage of chess pieces with an array ,dp Just transfer

IIIDX

The unlocking of each kind of music depends on each other , This dependency forms a tree

Change the meaning of the question to ： Every chain of a tree from top to bottom is monotonous , And make the node with larger number have larger weight

Consider that there is no same weight

obviously , The value of all nodes in the subtree of a node directly affects the value of the parent node , If a node wants to get the maximum value , If and only if all its subtree nodes get the maximum value

Greed is all

But with the same weight , As a result, the node can still get the maximum value when the subtree does not necessarily get the maximum value

Will find , It is not necessarily the optimal case that the subtree gets the maximum value , Because other nodes on the same layer of this node may take this value

Process each node in order , Reach a node , This node must take the maximum possible value

Then its subtree must be less than or equal to this number , You need to subtract the possible values of the subtree before considering the following values

Take the maximum number of this value each time , Make room for the remaining points

Line tree maintenance , Sort the optional values from large to small , Each point maintains the previous remaining total number , Each selection condition is that the value of all subsequent points is greater than or equal to the value of this point size

#include<bits/stdc++.h>
using namespace std;
bool cmp(int x,int y){
	return x>y;
}
struct node{
	int tot,tag;
};
struct segment_tree{
	node tr[2000100];
	void push_down(int id,int l,int r){
		tr[id].tot+=tr[id].tag;
		if(l!=r) tr[id<<1].tag+=tr[id].tag,tr[id<<1|1].tag+=tr[id].tag;
		tr[id].tag=0;
	}
	void upd(int id,int l,int r,int x,int y,int w){
		if(l>r) return ;
		if(x<=l&&r<=y){
			tr[id].tag+=w;
			push_down(id,l,r);
			return ;
		}
		push_down(id,l,r);
		int mid=(l+r)>>1;
		if(mid>=x) upd(id<<1,l,mid,x,y,w);
		if(mid<y) upd(id<<1|1,mid+1,r,x,y,w);
		push_down(id<<1,l,mid),push_down(id<<1|1,mid+1,r);
		tr[id].tot=min(tr[id<<1].tot,tr[id<<1|1].tot); 
	}
	int q_th(int id,int l,int r,int th){
		int mid=(l+r)>>1;
		if(l==r) return (tr[id].tot>=th?l:l+1);
		push_down(id<<1,l,mid),push_down(id<<1|1,mid+1,r);
		assert(tr[id].tot==min(tr[id<<1].tot,tr[id<<1|1].tot));
		if(th<=tr[id<<1|1].tot) return q_th(id<<1,l,mid,th);
		else return q_th(id<<1|1,mid+1,r,th); 
	}
};
segment_tree ty;
int a;
double b;
vector<int>tu[500010];
int sz[500010],fa[500010];
bool vis[500010];
void dfs(int x);
int ans[500010],ans_id[500010],w[500010],cnt[500010];
int main(){
	scanf("%d%lf",&a,&b);
	for(int i=1;i<=a;i++){
		scanf("%d",&w[i]);
	}
	sort(w+1,w+a+1,cmp);
	for(int i=1;i<=a;i++) ty.upd(1,1,a,i,i,i);
	for(int i=1;i<=a;i++){
		if(i/b) tu[(int)(i/b)].push_back(i),fa[i]=i/b;
	}
	for(int i=a-1;i>=1;i--) cnt[i]=(w[i]==w[i+1]?cnt[i+1]+1:0);
	for(int i=1;i<=a;i++){
		if(!vis[i]) dfs(i);
	}
	memset(vis,0,sizeof(vis));vis[0]=true;
	for(int i=1;i<=a;i++){
		if(!vis[fa[i]]) ty.upd(1,1,a,ans_id[fa[i]],a,sz[fa[i]]-1),vis[fa[i]]=true;
		int id=ty.q_th(1,1,a,sz[i]);
		id+=cnt[id],ans[i]=w[id];
		ans_id[i]=id;
		ty.upd(1,1,a,id,a,-sz[i]);
	}
	for(int i=1;i<=a;i++) printf("%d ",ans[i]);
	return 0;
}
void dfs(int x){
	vis[x]=true,sz[x]=1;
	for(int i=0;i<tu[x].size();i++){
		int p=tu[x][i];
		dfs(p);
		sz[x]+=sz[p];
	}
}

Split match  

Select the tutors in order , Ask everyone to choose a higher volunteer tutor first

Network flow , Dynamic edging , Because the calculation on the residual network after each edge addition will not affect the previous value

First, according to the ranking of each member , Then add a margin according to the order of each tutor , Just match

The second two points new ranking , Re dynamically add edges for judgment

Line tree merge

It is equivalent to completing the bitwise addition of two arrays in a better time

Every time you look down from the root , If both nodes have , Determine whether it is a leaf node , If it is a leaf node, it is added directly , Otherwise continue to merge , If one side is empty , Just take another node directly

The time complexity is related to the number of root additions , If whole program changes n The value of a point , The time complexity is O(nlogW)

The tail of a rainy day

The difference in the tree , Change the weights of four nodes each time

Each node opens a segment tree with the relief grain type as the node , Record the number of occurrences of each relief amount

Then merge the line segment tree from the leaf node upwards

Each time you query the location of the maximum value of each node