牛牛玩 generals 题解

1. 操作$11$：由于每头牛扩展的时候留下的兵是相同的，所以我们用set维护所有兵力相同的区间。

   扩展时消耗的兵力就是 $(r-l+1)\times p+\sum \mathrm{别}\mathrm{人}\mathrm{的}\mathrm{兵}\mathrm{力}-\sum \mathrm{自}\mathrm{己}\mathrm{的}\mathrm{兵}\mathrm{力}(r-l+1)\backslash times\; p\; +\backslash sum\; 别人的兵力-\backslash sum自己的兵力$。

   直接在 set 中遍历这些区间统计区间和。如果某个区间的一部分在 $l\sim rl\backslash sim\; r$ 中，将其拆成两段即可。

   而每次操作，除了两边的两个区间，中间被包含的区间访问后就会被删去。

   每次操作$11$只额外增加$O(1)O(1)$个区间，在整个过程中的区间总数为$O(n)O(n)$。

   所以对区间的操作总数是$O(n)O(n)$的。

   在std::set上加入、删除和分裂一个区间复杂度为$O(\log n)O(\backslash log\; n)$，因此操作$11$的总复杂度为$O(n\log n)O(n\backslash log\; n)$。

   然后考虑占领了某一个人的家的情况，我们可以使用并查集来维护某一个区间当前是属于谁的，

   当一个牛的$fa[x]=xfa[x]=x$表明它的家没有被占领，如果$yy$被$xx$占领了，那么我们令$fa[y]=xfa[y]=x$。

   所以对于每一次$11$操作，我们每次可以把所有家被占领的牛给存下来，然后把他们的$fafa$全部指向$xx$

   这样我们就可以使用并查集查询一个区间属于谁。

2. 操作$22$：在操作$11$时同步修改每头牛的兵力即可$O(1)O(1)$查询。

总时间复杂度为 $O(n\log n)O(n\; \backslash log\; n)$。

有部分选手可能写的较为复杂，std给出一种较为简洁的实现方式。

#include<bits/stdc++.h>
using namespace std;
#define M 100005
int mk[M];
struct hh{
	int l,r,w,p;//l,r表示区间的两个端点，w表示这段区间的兵力，我们存在set中的一段区间的兵力全部相同，p表示区间属于谁
	bool operator<(hh x)const{
		return l<x.l;
	}
};
set<hh>q;
set<hh>::iterator it;
int ans[M],a[M],fa[M],sk[M];
int find(int x){
	return fa[x]==x?x:fa[x]=find(fa[x]);//并查集维护当前区间属于谁
}
int main(){
	int n,m,t;
	scanf("%d%d%d",&n,&m,&t);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
		mk[a[i]]=i;fa[i]=i;
	}
	for(int i=1;i<=m;++i)q.insert((hh){i,i,0,mk[i]});//刚开始将所有区间***去，无主的格子就当属于0
	while(t--){
		int f;
		scanf("%d",&f);
		if(f==1){
			int x,l,r,p,cnt=0;
			scanf("%d%d%d%d",&x,&l,&r,&p);
			it=q.upper_bound((hh){r,0,0,0});
			int ans1=(r-l+1)*p,ans2=0,ans3=0;//ans1表示这段区间总兵力，ans2表示这段区间中自己的兵力，ans3表示别人的兵力
			--it;//找到左端点<=r的左后一个区间
			while(1){
				int l1=it->l,r1=it->r,w1=it->w,p1=it->p;
				if(r1<l)break;
				--it;//迭代器需要先把元素取出来再删除，否则会出事情
				q.erase((hh){l1,r1,w1,p1});
				p1=find(p1);//求出这个区间属于谁
				int l2=max(l1,l),r2=min(r1,r);//求区间交集
				if(p1==x)ans2+=w1*(r2-l2+1);//属于自己
				else{
					ans3+=w1*(r2-l2+1);//属于别人
					ans[p1]-=w1*(r2-l2+1);
					if(l2<=a[p1]&&r2>=a[p1])sk[++cnt]=p1;//把家被占领的存下来
				}
				if(l1<l)q.insert((hh){l1,l-1,w1,p1});//裂出左边部分
				if(r1>r)q.insert((hh){r+1,r1,w1,p1});//裂出右边部分
			}
			q.insert((hh){l,r,p,x});//插回去
			ans[x]+=ans1-ans2;
			printf("%d\n",ans1-ans2+ans3);
			for(int i=1;i<=cnt;++i)fa[sk[i]]=x,ans[x]+=ans[sk[i]];//更新并查集
		}
		else{
			int x;
			scanf("%d",&x);
			printf("%d\n",ans[x]);
		}
	}
	for(int i=1;i<=n;++i)if(fa[i]==i)printf("%d\n",i);
}