hdu5283 Senior's Fish(线段树+均摊分析)

传送门
考虑到每只鱼只会进网出网一次,于是直接建四棵线段树维护鱼的状态并建一棵树状数组维护答案即可。
注意有多组数据
代码:

#include<bits/stdc++.h>
#define ri register int
using namespace std;
const int rlen=1<<18|1;
inline char gc(){
	static char buf[rlen],*ib,*ob;
	(ib==ob)&&(ob=(ib=buf)+fread(buf,1,rlen,stdin));
	return *ib++;
}
inline int read(){
	int ans=0;
	bool f=1;
	char ch=gc();
	while(!isdigit(ch))f^=ch=='-',ch=gc();
	while(isdigit(ch))ans=((ans<<2)+ans<<1)+(ch^48),ch=gc();
	return f?ans:-ans;
}
typedef long long ll;
const int N=100005;
const ll inf=1e18;
int n,m,a[N][2];
bool f[N][2][2];
struct seg{
	#define lc (p<<1)
	#define rc (p<<1|1)
	#define mid (l+r>>1)
	ll mx[N<<2],add[N<<2];
	inline void pushup(int p){mx[p]=max(mx[lc],mx[rc]);}
	inline void pushnow(int p,ll v){add[p]+=v,mx[p]+=v;}
	inline void pushdown(int p){if(add[p])pushnow(lc,add[p]),pushnow(rc,add[p]),add[p]=0;}
	inline void build(int p,int l,int r,int op){
		add[p]=0;
		if(l==r){mx[p]=a[l][op];return;}
		build(lc,l,mid,op),build(rc,mid+1,r,op);
		pushup(p); 
	}
	inline void update(int p,int l,int r,int ql,int qr,ll v){
		if(ql<=l&&r<=qr)return pushnow(p,v);
		pushdown(p);
		if(qr<=mid)update(lc,l,mid,ql,qr,v);
		else if(ql>mid)update(rc,mid+1,r,ql,qr,v);
		else update(lc,l,mid,ql,qr,v),update(rc,mid+1,r,ql,qr,v);
		pushup(p);
	}
	inline int query(int p,int l,int r){
		if(l==r)return mx[p]=-inf,l;
		pushdown(p);
		int ret;
		return ret=mx[lc]==mx[p]?query(lc,l,mid):query(rc,mid+1,r),pushup(p),ret;
	}
	#undef lc
	#undef rc
	#undef mid
}Ax,Bx,Ay,By;
struct Bit{
	int Tim,bit[N],tim[N];
	Bit(){Tim=0;}
	inline void update(int p,int v){for(;p<=n;p+=(p&(-p)))bit[p]=tim[p]==Tim?bit[p]+v:(tim[p]=Tim,v);}
	inline int query(int p){int ret=0;for(;p;p^=(p&(-p)))ret+=tim[p]^Tim?0:bit[p];return ret;} 
}bt;
int X1,X2,Y1,Y2;
inline bool check(int x){return f[x][0][0]&&!f[x][0][1]&&f[x][1][0]&&!f[x][1][1];}
inline void clear(){
	int v;
	while(Ax.mx[1]>=X1){
		v=Ax.query(1,1,n);
		f[v][0][0]=1;
		if(check(v))bt.update(v,1);
	}
	while(Ay.mx[1]>=Y1){
		v=Ay.query(1,1,n);
		f[v][1][0]=1;
		if(check(v))bt.update(v,1);
	}
	while(Bx.mx[1]>X2){
		v=Bx.query(1,1,n);
		if(check(v))bt.update(v,-1);
		f[v][0][1]=1;
	}
	while(By.mx[1]>Y2){
		v=By.query(1,1,n);
		if(check(v))bt.update(v,-1);
		f[v][1][1]=1;
	}	
}
int main(){
	for(ri tt=read();tt;--tt){
		++bt.Tim;
		n=read(),X1=read(),Y1=read(),X2=read(),Y2=read();
		for(ri i=1;i<=n;++i){
			for(ri j=0;j<2;++j)a[i][j]=read();
			f[i][0][0]=f[i][1][0]=f[i][0][1]=f[i][1][1]=0;
		}
		Ax.build(1,1,n,0),Bx.build(1,1,n,0);
		Ay.build(1,1,n,1),By.build(1,1,n,1);
		clear();
		for(ri op,l,r,v,tt=read();tt;--tt){
			op=read(),l=read(),r=read();
			if(op==1)v=read(),Ax.update(1,1,n,l,r,v),Bx.update(1,1,n,l,r,v);
			if(op==2)v=read(),Ay.update(1,1,n,l,r,v),By.update(1,1,n,l,r,v);
			if(op^3)clear();
			else cout<<bt.query(r)-bt.query(l-1)<<'\n';
		}
	}
	return 0;
}
上一篇:牛客刷题Java实现----翻转单词顺序列


下一篇:我的DOJO学习之路(三)-几个DEMO