自动搬运

查看原文

来自洛谷，原作者为

	skkkh unwavering

搬运于2025-08-24 23:11:51，当前版本为作者最后更新于2025-04-17 13:38:15，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

KTSC怎么这么难？！！！

下文中将把一个可行的连接方案 $l,r$ 记作特殊区间 $[l,r]$。一个显然的结论是，任意两个特殊区间不可能相交（拥有共同端点不算相交），因为此时端点值较大的区间的两个端点之一必然被值较小的区间包含，从而阻断那个区间。因此，如果将特征区间的包含关系视作父子关系，那么所有特征区间将形成森林的结构。

当产生修改时，若修改值比当前值更大，则会删去从包含当前点最深的区间开始的一段树上祖先后代链，然后加入 $O(1)$ 个点并连上其对应的边。但若修改值比当前值小，则变化不好刻画。于是考虑对修改进行分治，令所有修改的位置初始为 $0$，每次向两侧递归时就将另一侧的修改加入并计算影响，就可以以 $O(\log Q)$ 的代价将修改全部转化为只增不减。

此时直接对序列再进行分治，用线段树维护就可以做到 $O(N \log N \log^2 Q)$，或者用 LCT 等数据结构直接维护树的形态做到 polylog，但実装がかなり大変です,并未完全发掘本题的性质。

我们发现修改的影响形式很特殊，一个修改只会在树上产生两处突变点，并新增 $O(1)$ 个点。如果对这些突变点建出虚树，那么删去虚树中的点后产生的每一个联通块都是一个等价类，可以将一个等价类缩成一个点。如果一颗树里没有突变点，就意味着后续加入的修改不会影响这颗树给答案的贡献，直接计算其贡献即可。这样分治到 $[l,r]$ 内的修改时，森林中便只有 $O(r-l+1)$ 个点，当往两侧递归时，直接加入另一侧的修改并维护森林，复杂度降到 $O(N \log N \log Q)$。

实现时可以不用显式地记录森林的结构，因为将特殊区间按 $l$ 排序后就是该森林的一个 dfs 序，可以通过从左往右扫描线做到遍历森林，且能更便捷地支持加点删点。

代码写的比较依托，不懂的可以看这个。

#include<bits/stdc++.h>
using namespace std;

namespace streetlights{
	const int N=3e5+5;
	int n,m,a[N],pl[N],h[N];
	struct pii{int l,r,w,c;
		bool operator<(const pii &a)const{return l<a.l||l==a.l&&w>a.w;}
	}p[20][N],tp[N];
	struct itv{int l,r,w;
		bool operator<(const itv &a)const{return l<a.l;} 
	}q[20][N],tq[N];
	int mx[N],de=131072;int td[N];
	int tx[20][N],pt[N],ans[N],id[N];
	int ch[20][N];bool ex[N],nok[N];
	void chg(int x,int v){
		x+=de;mx[x]=v;
		while(x>1)x>>=1,mx[x]=max(mx[x<<1],mx[x<<1|1]);
	}
	int askl(int x,int v){x+=de-1;
		while(__builtin_popcount(x)>1&&mx[x]<v)x=(x-1)>>1;
		if(mx[x]<v)return 0;
		while(x<=de)x=x<<1|(mx[x<<1|1]>=v);
		return (mx[x]==v?x-de:0);
	}
	int askr(int x,int v){x+=de+1;
		while(__builtin_popcount(x+1)>1&&mx[x]<v)x=(x+1)>>1;
		if(mx[x]<v)return 0;
		while(x<=de)x=x<<1|(mx[x<<1]<v);
		return (mx[x]==v?x-de:0);
	}
	void work(int d,int &cp,int cq){
		memcpy(q[d+1],q[d],(cq+1)*sizeof(itv));
		int c=0,px=0,cx=0;
		for(int i=1;i<=cq;i++)
			if(ch[d][i]){q[d+1][i].w=0;
				px=askl(q[d+1][i].l,ch[d][i]);
				if(px){
					px=upper_bound(q[d+1],q[d+1]+cq+1,(itv){px,0,0})-q[d+1]-1;
					tp[++c]={px,i,ch[d][i],1};
				}px=askr(q[d+1][i].l,ch[d][i]);
				if(px){
					px=upper_bound(q[d+1],q[d+1]+cq+1,(itv){px,0,0})-q[d+1]-1;
					if(!ch[d][px])tp[++c]={i,px,ch[d][i],1};
				}
			}
		sort(tp+1,tp+c+1);px=1;
		memset(nok,0,(cp+1)*sizeof(bool));
		for(int i=1;i<=cq;i++){
			while(cx&&p[d][td[cx]].r==i)cx--;
			while(px<=cp&&p[d][px].l==i)td[++cx]=px,px++;
			if(ch[d][i])while(cx&&p[d][td[cx]].w<=ch[d][i])nok[td[cx]]=1,cx--;
		}px=cx=1;int cl=0;
		while(px<=cp||cx<=c){
			while(px<=cp&&nok[px])px++;
			if(px>cp&&cx>c)break;
			if(cx>c||px<=cp&&cx<=c&&(p[d][px].l<tp[cx].l||p[d][px].l==tp[cx].l&&p[d][px].w>tp[cx].w))
				p[d+1][++cl]=p[d][px],px++;
			else p[d+1][++cl]=tp[cx],cx++;
		}cp=cl;
	}
	bool cmp(int x,int y){return pl[x]<pl[y];}
	int gp(int x,int y,int z){
		int l=1,r=y,md,an=0;
		while(l<=r){
			md=(l+r)>>1;
			if(p[z][td[md]].w<=x)an=md,r=md-1;
			else l=md+1;
		}return td[an];
	}
	void solve(int d,int lx,int rx,int cp,int cq,int an){
		if(lx==rx){
			for(int i=1;i<=cp;i++)
				an+=p[d][i].c*(p[d][i].r<pl[lx]||p[d][i].l>pl[lx]||p[d][i].w>h[lx]);
			ans[lx]=an+(askl(q[d][pl[lx]].l,h[lx])>0)+(askr(q[d][pl[lx]].l,h[lx])>0);return;
		}int mid=(lx+rx)>>1;int c=0;
		for(int i=1;i<=cq;i++){
			if(c&&!(q[d][i].w|tq[c].w))tq[c].r=q[d][i].r;
			else tq[++c]=q[d][i];id[i]=c;
		}cq=c;memcpy(q[d],tq,(c+1)*sizeof(itv));
		for(int i=lx;i<=rx;i++)
			tx[d][i]=pl[i],pl[i]=id[pl[i]],pt[i]=i;
		stable_sort(pt+lx,pt+rx+1,cmp);c=0;
		for(int i=1;i<=cp;i++){
			p[d][i].l=id[p[d][i].l],p[d][i].r=id[p[d][i].r];
			if(p[d][i].l==p[d][i].r)an+=p[d][i].c;else tp[++c]=p[d][i];
		}cp=c;memcpy(p[d],tp,(c+1)*sizeof(pii));c=0;int tl=1,tr=lx;
		for(int i=1;i<=cq;i++){
			while(c&&p[d][td[c]].r==i)c--;
			while(tl<=cp&&p[d][tl].l==i)td[++c]=tl,tl++;
			if(q[d][i].w){
				ex[gp(a[q[d][i].l],c,d)]=1;
				while(tr<=rx&&pl[pt[tr]]<=i){
					if(pl[pt[tr]]==i)ex[gp(h[pt[tr]],c,d)]=1;tr++;
				}
			}
		}c=0;
		for(int i=1;i<=cp;i++){
			if(!ex[i]&&c&&tp[c].l==p[d][i].l&&tp[c].r==p[d][i].r)
				tp[c].c+=p[d][i].c;else tp[++c]=p[d][i];ex[i]=0;
		}cp=c;memcpy(p[d],tp,(c+1)*sizeof(pii));
		for(int i=1;i<=cq;i++)ch[d][i]=q[d][i].w?a[q[d][i].l]:0;
		for(int i=lx;i<=mid;i++)ch[d][pl[i]]=0;
		for(int i=1;i<=cq;i++)if(ch[d][i])chg(q[d][i].l,ch[d][i]);
		work(d,(c=cp),cq);solve(d+1,lx,mid,c,cq,an);
		for(int i=lx;i<=mid;i++)a[q[d][pl[i]].l]=h[i];
		for(int i=1;i<=cq;i++)if(ch[d][i])ch[d][i]=0,chg(q[d][i].l,0);
		for(int i=lx;i<=rx;i++)ch[d][pl[i]]=h[i];
		for(int i=mid+1;i<=rx;i++)ch[d][pl[i]]=0;
		for(int i=1;i<=cq;i++)if(ch[d][i])chg(q[d][i].l,ch[d][i]);
		work(d,(c=cp),cq);solve(d+1,mid+1,rx,c,cq,an);
		for(int i=1;i<=cq;i++)if(ch[d][i])ch[d][i]=0,chg(q[d][i].l,0);
		for(int i=lx;i<=rx;i++)pl[i]=tx[d][i];
	}
	vector<long long int> streetlights_main(){
		chg(0,1e9),chg(n+1,1e9);
		for(int i=1;i<=n;i++)chg(i,a[i]);int px,c=0;
		for(int i=1;i<=n;i++)ans[0]+=(askl(i,a[i])>0);
		for(int i=1;i<=n;i++)q[1][i]={i,i,0};
		for(int i=1;i<=m;i++)q[1][pl[i]].w=1;
		for(int i=1;i<=n;i++)if(q[1][i].w)chg(i,0);
		for(int i=1;i<=n;i++)
			if(!q[1][i].w)if(px=askr(i,a[i]))p[1][++c]={i,px,a[i],1};
		solve(1,1,m,c,n,0);vector<long long int> res;
		for(int i=0;i<=m;i++)res.push_back(ans[i]);
		return res;
	}
}

vector<long long int> count_cable(vector<int> A, vector< pair<int, int> > C){
	streetlights::n=A.size();streetlights::m=C.size();
	for(int i=0;i<streetlights::n;i++)streetlights::a[i+1]=A[i];
	for(int i=0;i<streetlights::m;i++)
		streetlights::pl[i+1]=C[i].first,streetlights::h[i+1]=C[i].second;
	return streetlights::streetlights_main();
}