发布于

lp1438 无聊的数列

区间加上一个等差数列这件事情其实并不好维护。但既然是单点查询，那就可以考虑差分。
我们考虑将数列差分，维护一个差分数列。于是区间 [l,r] 加上等差数列 {K,D}，就变成了三个操作：
点 l 加上 K
区间 [l+1,r] 加上 D
点 r+1 减去 K+(r-l)*D
对于每个查询求前缀和即可。

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

const int N=100005;
int n,m;
ll a[N];
ll val[N<<2],tag[N<<2];
inline void pshd(int L,int R,int X){
	int MID=(L+R)>>1;
	tag[X<<1]+=tag[X];tag[X<<1|1]+=tag[X];
	val[X<<1]+=tag[X]*(MID-L+1);val[X<<1|1]+=tag[X]*(R-MID);
	tag[X]=0;
}
inline void updt(int X){
	val[X]=val[X<<1]+val[X<<1|1];
}
ll qry(int L,int R,int A,int B,int X){
	if(A<=L&&B>=R){
		return val[X];
	}
	int MID=(L+R)>>1;ll ret=0;
	pshd(L,R,X);
	if(A<=MID){
		ret+=qry(L,MID,A,B,X<<1);
	}
	if(B>MID){
		ret+=qry(MID+1,R,A,B,X<<1|1);
	}
	return ret;
}
void mdf(int L,int R,int A,int B,int X,ll V){
	if(A<=L&&B>=R){
		tag[X]+=V;
		val[X]+=V*(R-L+1);
		return;
	}
	int MID=(L+R)>>1;
	pshd(L,R,X);
	if(A<=MID){
		mdf(L,MID,A,B,X<<1,V);
	}
	if(B>MID){
		mdf(MID+1,R,A,B,X<<1|1,V);
	}
	updt(X);
}
void build(int L,int R,int X){
	if(L==R){
		val[X]=a[L];
		return;
	}
	int MID=(L+R)>>1;
	build(L,MID,X<<1);
	build(MID+1,R,X<<1|1);
	updt(X);
}
inline void chg(int L,int R,ll V){
	if(L>R||L<1||R>n){
		return;
	}
	mdf(1,n,L,R,1,V);
}
inline void init(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		scanf("%lld",&a[i]);
	}
	for(int i=n;i>1;--i){
		a[i]-=a[i-1];
	}
	build(1,n,1);
	ll opt,l,r,k,d,p;
	for(int i=1;i<=m;++i){
		scanf("%lld",&opt);
		if(opt==1){
			scanf("%lld%lld%lld%lld",&l,&r,&k,&d);
			chg(l,l,k);chg(l+1,r,d);chg(r+1,r+1,-(k+d*(r-l)));
		}else{
			scanf("%lld",&p);
			printf("%lld\n",qry(1,n,1,p,1));
		}
	}
}

int main(){
	init();
	return 0;
}
发布于

P1083 NOIP2012 借教室

本质上是区间减区间最小值。
考虑到先操作再询问，差分加前缀和即可。
对于题目要求的那个答案，我们找到第一个不合法的点，然后枚举每一个询问和它比较即可
复杂度O(n+m)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
 
typedef long long ll;
const int N=1000005;
ll a[N],val[N];
int qx[N],ql[N],qr[N];
int n,m;
void init(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		scanf("%lld",&a[i]);
	}
	for(int i=1;i<=m;++i){
		scanf("%d%d%d",&qx[i],&ql[i],&qr[i]);
		val[ql[i]]+=qx[i],val[qr[i]+1]-=qx[i];
	}
	int loc=0;
	for(int i=1;i<=n;++i){
		val[i]+=val[i-1];
		if(val[i]>a[i]){
			loc=i;
			break;
		}
	}
	if(!loc){
		puts("0");
		return;
	}
	ll cnt=0;
	for(int i=1;i<=m;++i){
		if(ql[i]<=loc&&qr[i]>=loc){
			if(cnt+qx[i]>a[loc]){
				puts("-1");
				printf("%d\n",i);
				return;
			}else{
				cnt+=qx[i];
			}
		}
	}
}
int main(){
	init();
	return 0;
}
发布于

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;
}
发布于

lp3320 SDOI2015 寻宝游戏

我们找到了这样一个结论：
「一个树上点集构成的最小生成树中，若两点间有路径，则此两点的DFS序在树上相近。」
这个结论的证明是较为困难的，但是感性理解还是比较容易的。
有了这个结论，我们就可以解决这一题。
每当一个新的点x即将加入点集的时候，我们只需要计算点集中DFS序刚好比它小的点y和DFS序刚好比它大的点z，然后将答案加上如下的式子：
$$dis_{x,y}+dis_{x,z}-dis_{y,z}$$
删去的时候逆向操作即可。
维护点集可以使用set。（善用STL（大雾））计算路径长度可以LCA+容斥。

注意：记得开long long 

#include<iostream>
#include<cstdio>
#include<set>

struct ee{
	int v;
	int w;
	int nxt;
}e[200005];
int h[100005],et=0;
inline void add(int U,int V,int W){
	e[++et]=(ee){V,W,h[U]};
	h[U]=et;
}
int fa[100005][30],dfn[100005],loc[100005],dep[100005],cnt=0;
long long val[100005];
//注意将两种深度分开。 
inline void dfs(int X,int FA){
	fa[X][0]=FA,dfn[X]=++cnt,loc[cnt]=X,dep[X]=dep[FA]+1;
	for(int i=h[X];i;i=e[i].nxt){
		if(e[i].v!=FA){
			val[e[i].v]=val[X]+e[i].w;
			dfs(e[i].v,X);
		}
	}
}

inline int lca(int X,int Y){
	if(dep[X]<dep[Y]){
		std::swap(X,Y);
	}
	for(int i=20;i>=0;--i){
		if(dep[X]-(1<<i)>=dep[Y]){
			X=fa[X][i];
		}
	}
	if(X==Y){
		return X;
	}
	for(int i=20;i>=0;--i){
		if(fa[X][i]!=fa[Y][i]){
			X=fa[X][i];
			Y=fa[Y][i];
		}
	}
	return fa[X][0];
}

inline long long dis(int X,int Y){
	return val[X]+val[Y]-(val[lca(X,Y)]<<1);
}

int n,m;
long long ans=0;
bool vis[100005];
std::set<int> s;
void init(){
	scanf("%d%d",&n,&m);
	int u,v,w;
	for(int i=1;i<n;++i){
		scanf("%d%d%d",&u,&v,&w);
		add(u,v,w);
		add(v,u,w);
	}
	dfs(1,0);
	for(int j=1;j<=20;++j){
		for(int i=1;i<=n;++i){
			fa[i][j]=fa[fa[i][j-1]][j-1];
		}
	}
	int x,y,z;
	long long d;
	std::set<int>::iterator it;
	for(int i=1;i<=m;++i){
		scanf("%d",&x);
		x=dfn[x];
		if(!vis[loc[x]]){
			s.insert(x);
		}
		y=loc[(it=s.lower_bound(x))==s.begin()?*--s.end():*--it];
		z=loc[(it=s.upper_bound(x))==s.end()?*s.begin():*it];
		//注意运算符优先级。 
		if(vis[loc[x]]){
			s.erase(x);
		}
		x=loc[x];
		d=dis(x,y)+dis(x,z)-dis(y,z);
		if(!vis[x]){
			vis[x]=1;
			ans+=d;
		}else{
			vis[x]=0;
			ans-=d;
		}
		//注意前后的x不是一个x 
		printf("%lld\n",ans);
	}
}

int main(){
	init();
	return 0;
}
发布于

NOIP2018 铺设道路

题意简述：
有一个序列，你可以一次将一个连续的段-1，但是不能让一个段变成0，求最小变成全零的操作次数。
方法有很多，个人的做法是差分以后把所有正值加起来。
没有细节，NOIP2013原题，完全就是为了送分。
感谢良心出题人。

#include<iostream>
#include<cstdio>
int n,a[100010],da[100010];

void init(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",a+i);
	}
	for(int i=1;i<=n;++i){
		da[i]=a[i]-a[i-1];
	}
	int sm=0;
	for(int i=1;i<=n;++i){
		da[i]=std::max(da[i],0);
		sm+=da[i];
	}
	printf("%d\n",sm);
}
int main(){
	init();
	return 0;
}