牛牛玩 generals 题解

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

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

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

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

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

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

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

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

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

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

这样我们就可以使用并查集查询一个区间属于谁。
操作 $2$ ：在操作 $1$ 时同步修改每头牛的兵力即可 $O (1)$ 查询。

总时间复杂度为 $O(n \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);
}