Solution P14380 | Easy Data Structure

若

f(l+1,r)\neq f(l,r)

且

f(l,r-1)\neq f(l,r)

，将

[l,r]

视作极小区间。问题转化为计算

[L,R]

中有多少个极小区间。

对于每个

i

求出最大的

r

使得

f(i,r)\neq f(i+1,r)

，记作

ar_i

；同时求出最小的

l

使得

f(l,i)\neq f(l,i-1)

，记作

al_i

。

那么极小区间的判定变成了

r\le ar_l

且

l\ge al_r

。

令

b(l,r) \in \{0,1\}

表示

[l,r]

是否极小。查询可以看作在

b

上矩形求和。用二维前缀和拆掉考虑。

对

r

扫描线，用历史和线段树维护即可。

CPP

int n,q,dfn[500005],out[500005],tim,al[500005],ar[500005],l[500005],r[500005];
vector<int>E[500005];

void dfs(int x,int fa){
	dfn[x]=(++tim);
	for(auto y: E[x]){
		if(y==fa) continue;
		dfs(y,x);
	}
	out[x]=tim;
}
void chkmax(int &a,int b){ if(b>a) a=b; }
namespace zkw{
	int n,c[2000005];
	void init(int _n){
		for(n=1;n<_n;n<<=1);
		for(int i=0;i<(n<<1);i++) c[i]=0;
	}
	void upd(int x,int w){
		for(x+=n-1;x;x>>=1) chkmax(c[x],w);
	}
	int qry(int l,int r){
		int ret=0;
		for(l+=n-1,r+=n;l<r;l>>=1,r>>=1){
			if(l&1) chkmax(ret,c[l++]);
			if(r&1) chkmax(ret,c[--r]);
		}
		return ret;
	}
}
namespace seg{
	int cnt[2000005],tag[2000005]; ll val[2000005];
	void upd(int pos,int v){
		tag[pos]+=v;
		val[pos]+=1ull*v*cnt[pos];
	}
	void pushdown(int pos){
		if(tag[pos]){
			upd(pos<<1, tag[pos]), upd(pos<<1|1, tag[pos]);
			tag[pos]=0;
		}
	}
	void pushup(int pos){
		val[pos]=val[pos<<1]+val[pos<<1|1];
		cnt[pos]=cnt[pos<<1]+cnt[pos<<1|1];
	}
	void update(int l,int r,int ql,int qr,int pos){
		if(qr<l || r<ql) return;
		if(ql<=l && r<=qr){
			upd(pos, 1);
			return;
		}
		int mid=(l+r)>>1; pushdown(pos);
		update(l,mid,ql,qr,pos<<1);
		update(mid+1,r,ql,qr,pos<<1|1);
		pushup(pos);
	}
	void modify(int l,int r,int x,int s,int pos){
		if(l==r){ cnt[pos]=s; return; }
		int mid=(l+r)>>1; pushdown(pos);
		if(x<=mid) modify(l,mid,x,s,pos<<1);
		else modify(mid+1,r,x,s,pos<<1|1);
		pushup(pos);
	}
	ll query(int l,int r,int ql,int qr,int pos){
		if(qr<l || r<ql) return 0;
		if(ql<=l && r<=qr) return val[pos];
		int mid=(l+r)>>1; pushdown(pos);
		return query(l,mid,ql,qr,pos<<1)+query(mid+1,r,ql,qr,pos<<1|1);
	}
}
vector<int>vec[500005];
vector<pair<int,int>>qry[500005];
ll ans[500005];

void procedure(){
	n=read(),q=read();
	for(int i=1;i<n;i++){
		int x=read(),y=read();
		E[x].pb(y), E[y].pb(x);
	}	
	dfs(1,0);
	zkw::init(n);
	for(int i=1;i<=n;i++){
		vector<int>cur;
		for(auto j: E[i]){
			if(dfn[j]<dfn[i]) cur.pb(max(zkw::qry(1,dfn[i]-1),zkw::qry(out[i]+1,n)));
			else cur.pb(zkw::qry(dfn[j],out[j]));
		}
		if(cur.size()>=2){ 
			sort(cur.begin(), cur.end(), greater<int>());
			al[i]=cur[1]+1;
		}else al[i]=1;
		zkw::upd(dfn[i],i);
	}
	zkw::init(n);
	for(int i=n;i>=1;i--){
		vector<int>cur;
		for(auto j: E[i]){
			if(dfn[j]<dfn[i]) cur.pb(max(zkw::qry(1,dfn[i]-1),zkw::qry(out[i]+1,n)));
			else cur.pb(zkw::qry(dfn[j],out[j]));
		}
		if(cur.size()>=2){ 
			sort(cur.begin(), cur.end(), greater<int>());
			ar[i]=n-cur[1];
		}else ar[i]=n;
		zkw::upd(dfn[i],n-i+1);
		vec[i].pb(i), vec[ar[i]+1].pb(-i);
	}

	for(int i=1;i<=q;i++){
		l[i]=read(),r[i]=read();
		qry[l[i]-1].pb(l[i]-1,i), qry[l[i]-1].pb(r[i],-i);
		qry[r[i]].pb(l[i]-1,-i), qry[r[i]].pb(r[i],i);
	}
	for(int r=1;r<=n;r++){
		for(auto x: vec[r]){
			if(x>0) seg::modify(1,n,x,1,1);
			else seg::modify(1,n,-x,0,1);
		}
		seg::update(1,n,al[r],r,1);

		for(auto [x,y]: qry[r]){
			ll val=seg::query(1,n,1,x,1);

			if(y>0) ans[y]+=val;
			else ans[-y]-=val;
		}
	}

	for(int i=1;i<=q;i++){
		printf("%lld\n",ans[i]);
	}
}

Solution P14380 | Easy Data Structure

文章操作

相关推荐

评论

Solution P14380 | Easy Data Structure