[Ynoi2012] NOIP2015 充满了希望(扫描线+线段树)

月心绽放的末日 / 2023-08-04 / 原文

题目传送门

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;
}