lp3168 CQOI2015 任务查询系统

观察题面,我们发现这是一道变态题:区间加点,单点查询第k大,强制在线——这tm不是变态题么!别的不说,权值怎么离散化我都不会。
仔细一看,真的是这样么?
我们发现,先是m个修改,后面再跟着n个询问!这意味着什么?这意味着所谓的区间修改事实上是fake的,因为我们事实上只要对最后一个版本进行询问。
经验上,多次区间修改后求单点值,我们使用差分+前缀和来维护。在这里同样是生效的,只需把每一次修改拆成两次即可。
修改可以用一些妙妙方式储存,比如说Vector或者手写邻接表。
那就是主席树裸题了。

注意:每一次修改的时候修改的仅仅是L和R+1两个点,但是这并不是正确的!在把修改排序之后,每一个修改是从它的上一个点复制版本,但上一个版本可能并没有任何修改,这也就意味着,上一个版本可能是空的!这就完全不是前缀和了。
应当如何做呢?每一个点应当预先从前一个点复制。这样哪怕这个点没有被修改,也仍然能保持它的性质。
另外,离散化的时候不应该把点离散化在一起。在这里,把值相同的点离散化到不同的位置并不会影响答案。事实上,如果把值相同的点离散化到相同的位置,反而会更麻烦。这是因为如果离散化到相同的位置,那么这三个点在线段树上就存在同一个点里了。这时候,倘若这个点的大小为3,而你需要查询前2大的和,你就无法处理了。这平白增加了实现的复杂度。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector> 
using namespace std;

typedef long long ll; 
const int N=100005;
inline int Abs(int X){
	return X>0?X:-X;
}
#define MID ((L+R)>>1) 
vector<int> lst[N];
struct data{
	int l;int r;int val;
}a[N];
inline bool cmp(const data &A,const data &B){
	return A.val<B.val;
}
int loc[N],vl[N];
int n,m;
class CMT{
	private:
		class Node{
			public:
				int l;int r;int sz;ll sm;
		}tr[N*160];
		int cnt,rt[N];
		inline void bld(int LST,int &NW,int L,int R,ll V){
			NW=++cnt;tr[NW].sz=tr[LST].sz+(V>0?1:-1);tr[NW].sm=tr[LST].sm+(V>0?loc[V]:-loc[-V]);
			if(L==R){return;}
			Abs(V)<=MID?(bld(tr[LST].l,tr[NW].l,L,MID,V),tr[NW].r=tr[LST].r):(bld(tr[LST].r,tr[NW].r,MID+1,R,V),tr[NW].l=tr[LST].l);
		}
		inline ll qry(int X,int L,int R,ll V){
			ll RT=0;
			while(L<R){
//				printf("%lld %d %d %d %lld %d\n",RT,X,L,R,V,tr[X].sz);
				(tr[tr[X].l].sz<V)?(L=MID+1,V-=tr[tr[X].l].sz,RT+=tr[tr[X].l].sm,X=tr[X].r):(R=MID,X=tr[X].l);
			}
			RT+=tr[X].sm;
			return RT;
		}
		inline void prnt(int X){
			if(!X){
				return;
			}
			printf("%d|%lld ",tr[X].sz,tr[X].sm);
			prnt(tr[X].l);prnt(tr[X].r);
		}
	public:
		inline void ADD(int X,ll V){
			int nw;
			if(!rt[X]){
				bld(rt[X-1],rt[X],1,100000,V);
			}else{
				bld(rt[X],nw,1,100000,V);
				rt[X]=nw;
			}
		}
		inline ll QRY(int X,int V){
//			printf("qry:%d %d %d\n",X,V,tr[rt[X]].sz);
			return V>tr[rt[X]].sz?tr[rt[X]].sm:qry(rt[X],1,100000,V);
		}
		inline void RNW(int X){
			if(!rt[X]){
				rt[X]=rt[X-1];
			}
		}
		inline void PRNT(int X){
			prnt(rt[X]);
		}
		inline void prpr(){
			cnt=0;
			tr[0].sz=tr[0].sm=0;
			for(int i=1;i<=n;++i){
				rt[i]=0;
			}
		}
}TR;
void init(){
	TR.prpr();
	scanf("%d%d",&m,&n);
	for(int i=1;i<=m;++i){
		scanf("%d%d%d",&a[i].l,&a[i].r,&a[i].val);
	}
	std::sort(a+1,a+1+m,cmp);
	vl[0]=0,a[0].val=0;
	for(int i=1;i<=m;++i){
		vl[i]=vl[i-1]+1;
		loc[vl[i]]=a[i].val;
	}
	for(int i=1;i<=m;++i){
		lst[a[i].l].push_back(vl[i]);
		lst[a[i].r+1].push_back(-vl[i]);
	}
	for(int i=1;i<=n;++i){
		TR.RNW(i);
		for(int j=0;j<lst[i].size();++j){
			TR.ADD(i,lst[i][j]);
		}
	}
	int x,a,b,c,v;ll lans=1;
	for(int i=1;i<=n;++i){
		scanf("%d%d%d%d",&x,&a,&b,&c);
		v=(1ll*lans*a+b)%c+1;
		printf("%lld\n",lans=TR.QRY(x,v));
	}
}
int main(){
	init();
	return 0;
}

lp3302 SDOI2013 森林

我们发现,树上的链上第k大是可以使用主席树来维护的。对于每一个节点,我们从它的父亲复制一个版本,然后每一次求出LCA以后对链的两个端点、链的LCA、链的父亲分别查询。之后统计答案即可。
对于有连边操作的树,我们可能可以想到用LCT来维护。但是代码难度太高,而且事实上我也不知道要怎么写。所以我们可以考虑一种类似于按秩合并的操作,也就是说,每一次,我们把子树大小较小的子树合并到子树大小较大的子树。对于较小的那棵树,我们暴力更新其中的每一个节点。于是可以证明,每个节点的被更新次数最多不超过log次。
这样我们就有了一个\(O(nlog^2n)\)的做法。
注意:主席树的L,R本身就是节点位置;合并的时候要记得更新小树的根节点;返回的值是第k大的值而非第k大的排名因而要逆离散化。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
using namespace std;

const int N=80005;
struct data{
	int id;
	int val;
}a[N];
inline bool cmp(const data &A,const data &B){
	return A.val<B.val;
}
inline bool cmp2(const data &A,const data &B){
	return A.id<B.id;
}
struct ee{
	int v;
	int nxt;
}e[N<<1];
int h[N],et=0;
inline void Eadd(int U,int V){
	e[++et]=(ee){V,h[U]};
	h[U]=et;
}
inline void add(int U,int V){
	Eadd(U,V),Eadd(V,U);
}
#define MID (L+R>>1)
class CMT{
	private:
		class Node{
			public:
				int l;int r;int sz;
		};
		Node tr[30000000];
		int cnt,rt[N];
		inline void bld(int LST,int &NW,int L,int R,int V){
			NW=++cnt;tr[NW].sz=tr[LST].sz+1;
			if(L==R){return;}
			V<=MID?(bld(tr[LST].l,tr[NW].l,L,MID,V),tr[NW].r=tr[LST].r):(bld(tr[LST].r,tr[NW].r,MID+1,R,V),tr[NW].l=tr[LST].l);
		}
		inline int qry(int A,int B,int C,int D,int L,int R,int V){
			while(L<R){
//				printf("nw:%d %d %d %d %d\n",A,B,C,D,V);
				(tr[tr[B].l].sz-tr[tr[A].l].sz+tr[tr[D].l].sz-tr[tr[C].l].sz<V)?
				(V-=tr[tr[B].l].sz-tr[tr[A].l].sz+tr[tr[D].l].sz-tr[tr[C].l].sz,L=MID+1,A=tr[A].r,B=tr[B].r,C=tr[C].r,D=tr[D].r):
				(R=MID,A=tr[A].l,B=tr[B].l,C=tr[C].l,D=tr[D].l);
			}
			return L;
		}
		inline void prnt(int X){
			if(!X){
				return;
			}
			prnt(tr[X].l);
			prnt(tr[X].r);
			printf("%d ",tr[X].sz);
		}
	public:
		inline void ADD(int LST,int VER,int V){
			bld(rt[LST],rt[VER],1,80000,V);
		}
		inline int QRY(int A,int B,int C,int D,int V){
			return qry(rt[A],rt[B],rt[C],rt[D],1,80000,V);
		}
		inline void prpr(){
			cnt=0;
		}
		inline void pt(int X){
			prnt(rt[X]);
		}
}TR;
int vis[N],fa[N][20],sz[N],dep[N],loc[N];
inline void dfs0(int X){
//	printf("\t\t\tdfs0(%d)%d\n",X,dep[X]);
	vis[X]=sz[X]=1;
	for(int i=h[X];i;i=e[i].nxt){
		if(vis[e[i].v]){
			continue;
		}
		fa[e[i].v][0]=X;
		dep[e[i].v]=dep[X]+1;
		for(int j=1;j<=18;++j){
			fa[e[i].v][j]=fa[fa[e[i].v][j-1]][j-1];
		}
		TR.ADD(X,e[i].v,a[e[i].v].val);
		dfs0(e[i].v);
		sz[X]+=sz[e[i].v];
	}
}
inline void dfs1(int X){
	vis[X]=0;
	for(int i=h[X];i;i=e[i].nxt){
		if(!vis[e[i].v]){
			continue;
		}
		dfs1(e[i].v);
	}
}
inline int szq(int X){
	for(int i=18;i>=0;--i){
		if(fa[X][i]!=0){
			X=fa[X][i];
		}
	}
	return sz[X];
}
inline void uni(int X,int Y){
	int SZ=szq(X);
	dfs1(X);
	add(X,Y);
	fa[X][0]=Y;
	dep[X]=dep[Y]+1;
	TR.ADD(Y,X,a[X].val);
	for(int i=1;i<=18;++i){
		fa[X][i]=fa[fa[X][i-1]][i-1];
	}
	int RT=X;
	for(int i=18;i>=0;--i){
		if(fa[RT][i]){
			RT=fa[RT][i];
		}
	}
	sz[RT]+=SZ;
	dfs0(X);
}
inline int lca(int X,int Y){
	if(dep[X]<dep[Y]){
		X^=Y^=X^=Y;
	}
	for(int i=18;i>=0;--i){
		if(dep[fa[X][i]]>=dep[Y]){
			X=fa[X][i];
		}
	}
	if(X==Y){
		return X;
	}
	for(int i=18;i>=0;--i){
		if(fa[X][i]!=fa[Y][i]){
			X=fa[X][i],Y=fa[Y][i];
		}
	}
	return fa[X][0];
}
int n,m,q,tid;
void init(){
	scanf("%d",&tid);
	scanf("%d%d%d",&n,&m,&q);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i].val);
		a[i].id=i;
	}
	std::sort(a+1,a+1+n,cmp);
	for(int i=1;i<=n;++i){
		loc[i]=a[i].val;
	}
	for(int i=1;i<=n;++i){
		if(a[i].val!=a[i-1].val){
			a[i].val=a[i-1].val+1;
		}else{
			a[i].val=a[i-1].val;
		}
	}
	std::sort(a+1,a+1+n,cmp2); 
	int u,v;
	for(int i=1;i<=m;++i){
		scanf("%d%d",&u,&v);
		add(u,v);
	}
	TR.prpr();
	for(int i=1;i<=n;++i){
		if(!vis[i]){
			dep[i]=1;
			TR.ADD(0,i,a[i].val);
			dfs0(i);
		}
	}
//	for(int i=1;i<n;++i){
//		printf("%d:",i);
//		TR.pt(i);
//		puts("");
//	}
	int lans=0,x,lc;
	char ch[10];
	for(int i=1;i<=q;++i){
		cin>>ch+1;
		switch(ch[1]){
			case 'Q':{
				scanf("%d%d%d",&u,&v,&x);
				u^=lans,v^=lans,x^=lans;
				lc=lca(u,v);
//				printf("\t\t\t%d %d %d\n",u,v,x);
				printf("%d\n",lans=loc[TR.QRY(fa[lc][0],u,lc,v,x)]);
				break; 
			}
			case 'L':{
				scanf("%d%d",&u,&v);
				u^=lans,v^=lans;
//				printf("\t\t\t%d %d\n",u,v);
				if(szq(u)>szq(v)){
					u^=v^=u^=v;
				}
				uni(u,v);
				break;
			}
		}
	}
}
int main(){
	init();
	return 0;
}

lp2468 SDOI2010 粟粟的书架

简化题意。
有一个n*m的矩阵,q个询问,求问,在每个矩阵中最少取多少个数,使得和至少为h。
观察数据范围,我们惊讶地发现这一题不可避免地要做两次。
因为,n,m<=200显然不是用普通的数据结构可以维护的。我们考虑使用\(cnt_{i,j,k}\)表示大于k的数的数量,\(sm_{i,j,k}\)表示大于k的数的总和。然后二分这个k来求解即可。
对于n==1的情况,我们很容易可以想到维护一棵权值主席树。对于每一个询问,我们在两棵权值线段树上二分然后求差。

#include<iostream>
#include<cstdio>
#define MID ((L+R)>>1)
int n,m,q;
int b[205][205],cnt[205][205][1005],sm[205][205][1005];
//不需要开longlong!!!MLE警告!!! 

inline long long cntQry(int X1,int Y1,int X2,int Y2,int K){
    return cnt[X2][Y2][K]-cnt[X1-1][Y2][K]-cnt[X2][Y1-1][K]+cnt[X1-1][Y1-1][K];
}
inline long long smQry(int X1,int Y1,int X2,int Y2,int K){
    return sm[X2][Y2][K]-sm[X1-1][Y2][K]-sm[X2][Y1-1][K]+sm[X1-1][Y1-1][K];
}
inline void slv2(){
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            scanf("%d",&b[i][j]);
        }
    }
    for(int k=0;k<=1000;++k){
        for(int i=1;i<=n;++i){
            for(int j=1;j<=m;++j){
                cnt[i][j][k]=cnt[i-1][j][k]+cnt[i][j-1][k]-cnt[i-1][j-1][k]+(int)(b[i][j]>=k);
                sm[i][j][k]=sm[i-1][j][k]+sm[i][j-1][k]-sm[i-1][j-1][k]+(int)(b[i][j]>=k)*b[i][j];
            }
        }
    }
    long long l,r,mid,h,ans;
    int X1,X2,Y1,Y2;
    while(q--){
        l=0,r=1001,ans=-1;
        scanf("%d%d%d%d%lld",&X1,&Y1,&X2,&Y2,&h);
        while(l<=r){
            mid=(l+r)>>1,smQry(X1,Y1,X2,Y2,mid)>=h?(ans=mid,l=mid+1):r=mid-1;
        }
        (~ans)?(printf("%lld\n",cntQry(X1,Y1,X2,Y2,ans)-(smQry(X1,Y1,X2,Y2,ans)-h)/ans)):(puts("Poor QLW"));
    }
    
//	 对于同一个k可能有多个值,而可能只需要选取部分。 
}
const int MAXN2=10000005;
int a[MAXN2];
//数组大小别算错 
class ChairmanTree{
    private:
        class Node{
            public:
                int l;
                int r;
                int fa;
                int sz;
                int sm;
        };
        Node tr[MAXN2];
        int cnt,rt[MAXN2];
        inline void build(int LST,int &NW,int L,int R,int V){
            NW=++cnt;tr[NW].sz=tr[LST].sz+1;tr[NW].sm=tr[LST].sm+V;
            if(L==R){return;}
            MID>=V?(build(tr[LST].l,tr[NW].l,L,MID,V),tr[NW].r=tr[LST].r):(build(tr[LST].r,tr[NW].r,MID+1,R,V),tr[NW].l=tr[LST].l);
            //如果值小等于MID。那么就更新右边的值;否则更新左边的值。一定要注意判断V==MID时的情况。 
            //如果更新的是右边的值,那么就把右边的节点与上一个版本的右边的节点一并下传,并修改本节点的左节点;否则反之。 
        }
        //从根往下搜索。注意减去的应当是右节点的值。 
        inline int qry(int A,int B,int L,int R,int V){
            int RT=0;
            while(L<R){(tr[tr[B].r].sm-tr[tr[A].r].sm)>V?(L=MID+1,B=tr[B].r,A=tr[A].r):(RT+=tr[tr[B].r].sz-tr[tr[A].r].sz,V-=(tr[tr[B].r].sm-tr[tr[A].r].sm),R=MID,B=tr[B].l,A=tr[A].l);}
            //同理,对于等于的情况也应当特别注意。 
            return RT+(V+L-1)/(L);
            //剩下的部分应该全部由大小为R的这些东西,也就是当前点的值来处理掉。故而要加上(V+L-1)/(L)
        }
    public:
        inline void ADD(int VER,int X){
            build(rt[VER-1],rt[VER],1,1000,X);
        }
        inline int QUREY(int LVER,int RVER,int X){
            return qry(rt[LVER-1],rt[RVER],1,1000,X);
        }
        inline int SUM(int L,int R){
            return tr[rt[R]].sm-tr[rt[L-1]].sm;
        }
        inline void INIT(){
            cnt=0;
        }
};
ChairmanTree T;
inline void slv1(){
    T.INIT();
    for(int i=1;i<=m;++i){
        scanf("%d",&a[i]);
        T.ADD(i,a[i]);
    }
    int l,r,tmp,x;
    while(q--){
        scanf("%d%d%d%d%d",&tmp,&l,&tmp,&r,&x);
        if(T.SUM(l,r)<x){
            puts("Poor QLW");
            continue;
        }
        printf("%d\n",T.QUREY(l,r,x));
    }
}

void init(){
    scanf("%d%d%d",&n,&m,&q);
    n==1?slv1():slv2();
}

int main(){
    init();
    return 0;
}