题目传送门
solution
简单题。
我们正着做扫描线。
设 \(t_i\) 表示位置 \(i\) 最后一次进行二操作的时间，那么一操作就是交换 \(t_x,t_y\) ，二操作就是区间复制。
对于三操作，开一个树状数组，如果查询的位置的 \(t_x=j\)，就在 \(j\) 的位置上加一。
查询就是查询后缀和。
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+7;
int n,m,q;
int tag[N*4];
typedef long long LL;
LL C[N];
void upd(int x,LL v)
{
for(int i=x;i;i-=i&-i)C[i]+=v;
}
LL ask(int x)
{
LL res=0;
for(int i=x;i<=m;i+=i&-i)res+=C[i];
return res;
}
void pushdown(int k)
{
if(tag[k])
{
tag[k<<1]=tag[k];
tag[k<<1|1]=tag[k];
tag[k]=0;
}
}
void cov(int k,int l,int r,int L,int R,int c)
{
if(L<=l&&r<=R)
{
tag[k]=c;
return;
}
pushdown(k);
int mid=(l+r)>>1;
if(L<=mid)cov(k<<1,l,mid,L,R,c);
if(R>mid) cov(k<<1|1,mid+1,r,L,R,c);
}
int get(int k,int l,int r,int x)
{
if(l==r)return tag[k];
pushdown(k);
int mid=(l+r)>>1;
if(x<=mid) return get(k<<1,l,mid,x);
return get(k<<1|1,mid+1,r,x);
}
int a[N],b[N],c[N],d[N];
#define PII pair<int,int>
#define mk(x,y) make_pair(x,y)
#define X(x) x.first
#define Y(x) x.second
vector<PII> G[N];
LL Ans[N];
int main()
{
cin>>n>>m>>q;
for(int i=1;i<=m;i++)
{
scanf("%d %d",&a[i],&b[i]);
if(a[i]!=3)scanf("%d",&c[i]);
if(a[i]==2)scanf("%d",&d[i]);
}
for(int i=1;i<=q;i++)
{
int l,r;
scanf("%d %d",&l,&r);
G[r].push_back(mk(l,i));
}
for(int i=1;i<=m;i++)
{
if(a[i]==1)
{
int x=get(1,1,n,b[i]);
int y=get(1,1,n,c[i]);
cov(1,1,n,b[i],b[i],y);
cov(1,1,n,c[i],c[i],x);
}
else if(a[i]==2) cov(1,1,n,b[i],c[i],i);
else
{
int c=get(1,1,n,b[i]);
if(c) upd(c,d[c]);
}
for(auto U:G[i])Ans[U.second]=ask(U.first);
}
for(int i=1;i<=q;i++)printf("%lld\n",Ans[i]);
return 0;
}