利用fhq treap 解决了一道区间序列的问题.

题目是2020hdu多校第9场的一个题目.

题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=6873

代码留存

// 33897476	2020-09-09 23:28:50	Accepted	6873	3556MS	8516K	3787B	G++	mainland 
#include <bits/stdc++.h>
using namespace std;
#define inc(i,a,b) for(int i=a;i<=b;i++)
#define dec(i,a,b) for(int i=a;i>=b;i--)
#define ll long long 
#define mst(a,b) memset(a,b,sizeof a)
#define pb push_back
inline int read(){
	char ch=getchar();int f=1,x=0;
	while(!isdigit(ch)) { if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)){ x=x*10+ch-'0';ch=getchar();}
	return f*x;
}


//by Sshwy

int n,q;
const int SZ = 5e5+5;
// fhq treap 的模板
template<class T>
struct Treap{
	int root,tot;
	int mem[SZ],memp;
	int lc[SZ],rc[SZ],sz[SZ];
	unsigned int rnd[SZ];
	T val[SZ],mn[SZ];
	long long s[SZ];

	void clear(){
		fill(lc,lc+tot+1,0);
		fill(rc,rc+tot+1,0);
		fill(sz,sz+tot+1,0);
		root=tot=0;
	}

	Treap(){
		root=tot=0;
		srand(clock()+time(0));
		s[0] = val[0] = 0;
		mn[0]=1e9;
	}

	inline void pushup(int u){
		sz[u] = sz[lc[u]]+sz[rc[u]]+1;
		mn[u] = min(val[u],min(mn[lc[u]],mn[rc[u]]));
		s[u]=s[lc[u]]+s[rc[u]]+val[u];
	}

	void split(int u,const int left_size,int &x,int &y){
		if(!u)return x=y=0,void();
		if(sz[lc[u]]+1<=left_size)x=u,split(rc[u],left_size-sz[lc[u]]-1,rc[u],y);
		else y=u,split(lc[u],left_size,x,lc[u]);
		pushup(u);
	}

	//按住权值拆分为两颗子树
	void split_by_val(int now,const T k,int &x,int &y){
		if(!now) return x=y=0,void();
		if(val[now]<=k) x=now,split_by_val(rc[now],k,rc[now],y);
		else y=now,split_by_val(lc[now],k,x,lc[now]);
		pushup(now);

	}

	//按照排名拆分成两颗子树
	//和split其实是一样的　k = left_size
	void split_by_rank(int now,int k,int &x,int &y){
		if(!now) return x=y=0,void();
		if(sz[lc[now]]+1<=k) x=now,split_by_rank(rc[now],k-sz[lc[now]]-1,rc[now],y);
		else y=now,split_by_rank(lc[now],k,x,lc[now]);
		pushup(now);
	}

	//x,y两个子树,且所有的节点的值都小于y的所有节点的值
	//随机权重以小根堆的形式存储
	int merge(int x,int y){//x<y
		if(!x||!y)return x+y;
		//if(rand()%(sz[x]+sz[y])<sz[x])return rc[x]=merge(rc[x],y), pushup(x), x;
		if(rnd[x]<rnd[y])return rc[x]=merge(rc[x],y), pushup(x), x;
		else return lc[y]=merge(x,lc[y]), pushup(y), y;
	}

//虽然可能不满足堆的性质，但是，堆在这个过程中只是调节树的平衡的，所以还是可以过的	
	int dfs(int * a, int l,int r){
		if(l>r) return 0;
		int u=++tot,mid=l+r>>1;
		s[u]=val[u]=mn[u]=a[mid],sz[u]=r-l+1,rnd[u]=rand();
		lc[u]=dfs(a,l,mid-1);
		rc[u]=dfs(a,mid+1,r);
		pushup(u);
		return u;
	}

	void build_from(int *a,int l,int r){
		root=dfs(a,l,r);
	}

	void dfs_seq(int u,T *p){
		if(u==0) return;
		dfs_seq(lc[u],p);
		*(p+sz[lc[u]]+1) = val[u];
		dfs_seq(rc[u],p+sz[lc[u]]+1);
	}
	void seq(T *p){
		dfs_seq(root,p);
	}


	T kth(int k){
		int u=root;
		while(k!=sz[lc[u]]+1){
			if(k<=sz[lc[u]]) u=lc[u];
			else k-=sz[lc[u]]+1,u=rc[u];
		}
		return val[u];
	}

	void split_by_min(int now,const int right_mn,int &x,int &y){
		if(!now) return x=y=0,void();
		if(mn[rc[now]]<right_mn || val[now]< right_mn)
			x=now,split_by_min(rc[now],right_mn,rc[now],y);
		else y=now,split_by_min(lc[now],right_mn,x,lc[now]);
		pushup(now);
	}


	long long perform(int x,int y){
		if(kth(x)<y) return 0;
		int L,R;
		split_by_rank(root,x,L,R);
		if(mn[L]>=y) {
			root=merge(L,R);
			return 0;
		}
		int l,r;
		split_by_min(L,y,l,r);


		int l1,l2,r1,r2;
		ll res=s[r]-sz[r]*1LL*(y-1);

		split(l,sz[l]-1,l1,l2);
		split(r,1,r1,r2);
		val[l2]+=val[r1]-(y-1);
		s[l2]=mn[l2]=val[l2];
		s[r1]=mn[r1]=val[r1]=y-1;
		root=merge(merge(merge(l1,l2),merge(r2,r1)),R);
		return res;
	}

};

Treap<int> T;
const int N=2e5+5;
int b[N];
void go(){
	scanf("%d%d",&n,&q);
	T.clear();
	inc(i,1,n) scanf("%d",b+i);
	T.build_from(b,1,n);
	inc(i,1,q){
		int op,x,y;
		scanf("%d%d",&op,&x);
		if(op==1) scanf("%d",&y),printf("%lld\n",T.perform(x,y));
		else printf("%d\n",T.kth(x));
	}
	T.seq(b);
	inc(i,1,n) printf("%d%c",b[i]," \n"[i==n]);
}

int main(){ int t=read();while(t--) go();return 0; }