树套树

cwy posted @ 2018年1月10日 07:58 in 板子 , 47 阅读

BZOJ3196,T了一点

#include<cstdio>
#include<cstring>
#include<iostream>
#include<stdlib.h>
#include<ctime>
#include<string>
#include<cmath>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<queue>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define LL long long
#define FOR(i,a,b) for (int i=a;i<=b;i++)
#define FORD(i,a,b) for (int i=a;i>=b;i--)
using namespace std;
typedef pair<int,int> pa;
void getint(int &v){
    char ch,fu=0;
    for(ch='*'; (ch<'0'||ch>'9')&&ch!='-'; ch=getchar());
    if(ch=='-') fu=1, ch=getchar();
    for(v=0; ch>='0'&&ch<='9'; ch=getchar()) v=v*10+ch-'0';
    if(fu) v=-v;
}
const int INF=1e9+10;
struct node{
	int v,siz,cnt;
	int ch[2],fa;
}t[2000010];
int a[200010],tp,n,X,Y,m,ans,x,tot,rt[200010],l,r,k;
void debug(int x){
	if (t[x].ch[0]) debug(t[x].ch[0]);
	FOR(i,1,t[x].cnt) printf("%d ",t[x].v);
	if (t[x].ch[1]) debug(t[x].ch[1]);
}
void DEBUG(){
	FOR(i,1,n) debug(rt[i]),puts("");
	puts("**");
}
void pushup(int x){
	t[x].siz=t[t[x].ch[0]].siz+t[t[x].ch[1]].siz+t[x].cnt;
}
void rot(int x){
	int fa=t[x].fa;
	int gfa=t[fa].fa;
	int t1=(x!=t[fa].ch[0]);
	int t2=(fa!=t[gfa].ch[0]);
	int ch=t[x].ch[t1^1];
	if (gfa) t[gfa].ch[t2]=x;
	t[ch].fa=fa;
	t[x].fa=gfa;
	t[x].ch[t1^1]=fa;
	t[fa].fa=x;
	t[fa].ch[t1]=ch;
	pushup(fa);
	pushup(x);
}
void splay(int x,int too){
	while (t[x].fa!=too){
		int fa=t[x].fa;
		int gfa=t[fa].fa;
		if (gfa!=too)
			(x==t[fa].ch[0]^fa==t[gfa].ch[0])?rot(x):rot(fa);
		rot(x);
	}
}
int fnd(int x,int k){
	if (k<=t[t[x].ch[0]].siz) return fnd(t[x].ch[0],k);
	else if (k>t[t[x].ch[0]].siz+t[x].cnt) return fnd(t[x].ch[1],k-t[t[x].ch[0]].siz-t[x].cnt);
	else return x;
}
int rnk(int x,int k){
	if (!x) return 0;
	if (k<t[x].v) return rnk(t[x].ch[0],k);
	else if (k==t[x].v) return t[t[x].ch[0]].siz+t[x].cnt;
	else return t[t[x].ch[0]].siz+t[x].cnt+rnk(t[x].ch[1],k);
}
void ins(int &x,int v,int fa){
	if (!x){
		x=++tot;
		t[x].v=v;
		t[x].siz=t[x].cnt=1;
		t[x].fa=fa;
		return;
	}
	if (v==t[x].v) ++t[x].cnt;
	else if (v<t[x].v) ins(t[x].ch[0],v,x);
	else ins(t[x].ch[1],v,x);
	pushup(x);
}
void del(int x,int v){
	X=fnd(rt[x],rnk(rt[x],v-1));
	Y=fnd(rt[x],rnk(rt[x],v)+1);
	splay(X,0);
	rt[x]=X;
	splay(Y,X);
	--t[t[Y].ch[0]].cnt;
	pushup(t[Y].ch[0]);
	if (t[t[Y].ch[0]].cnt==0) t[Y].ch[0]=0;
	pushup(Y);
	pushup(X);
}
inline int lowbit(int x){
	return x&-x;
}
void ADD(int x,int T){
	for (;x<=n;x+=lowbit(x)){
		int tt=tot;
		ins(rt[x],T,0);
		if (tt!=tot){
			rt[x]=tot;
			splay(tot,0);
		}
	}
}
void DEL(int x,int t){
	for (;x<=n;x+=lowbit(x)){
		del(x,t);
	}
}
int SUM(int x,int t){
	int s=0;
	for (;x;x-=lowbit(x))
		s+=rnk(rt[x],t)-1;
	return s;
}
int main(){
//	freopen("t.in","r",stdin);
//	freopen("t.out","w",stdout);
	scanf("%d%d",&n,&m);
	FOR(i,1,n){
		rt[i]=++tot;
		t[rt[i]].v=-INF;
		t[rt[i]].ch[1]=++tot;
		t[tot].v=INF;
		t[tot].fa=tot-1;
		t[tot].cnt=t[tot].siz=1;
		t[tot-1].siz=1;
		t[tot-1].cnt=1;
		pushup(tot-1);
	}
	FOR(i,1,n) getint(a[i]),ADD(i,a[i]);
	while (m--){
		getint(tp);
		if (tp==1){
			getint(l),getint(r),getint(k);
			ans=(SUM(r,k-1)-SUM(l-1,k-1))+1;
			printf("%d\n",ans);
		}
		else if (tp==2){
			getint(l),getint(r),getint(k);
			int L=0,R=1e8;
			while (L<R){
				int O=L+R>>1;
				if (SUM(r,O)-SUM(l-1,O)>=k) R=O;
				else L=O+1;
			}
			printf("%d\n",R);
		}
		else if (tp==3){
			getint(x),getint(k);
			DEL(x,a[x]);
			a[x]=k;
			ADD(x,a[x]);
		}
		else if (tp==4){
			getint(l),getint(r),getint(k);
			k=SUM(r,k-1)-SUM(l-1,k-1);
			int L=0,R=1e8;
			while (L<R){
				int O=L+R>>1;
				if (SUM(r,O)-SUM(l-1,O)>=k) R=O;
				else L=O+1;
			}
			printf("%d\n",R);
		}
		else{
			getint(l),getint(r),getint(k);
			k=SUM(r,k)-SUM(l-1,k)+1;
			int L=0,R=1e8;
			while (L<R){
				int O=L+R>>1;
				if (SUM(r,O)-SUM(l-1,O)>=k) R=O;
				else L=O+1;
			}
			printf("%d\n",R);
		}
	}
	return 0;
}

http://codeforces.com/contest/785/submission/34064644

特技:不要从小往大insert,random_shuffle之后再insert


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter