Codeforces Round 921 (Div. 2) 赛后总结

#include <bits/stdc++.h>
using namespace std;
long long x[300005];
long long v[300005],he[300005],ne[300005],ans[300005],L[300005],R[300005];
long long read1()
{
	char cc=getchar();
	while(!(cc>=48&&cc<=57))
	{
		if(cc=='-')
		{
			break;
		}
		cc=getchar();
	}
	bool f=false;
	int s=0;
	if(cc=='-')
	{
		f=true;
	}
	else
	{
		s=cc-48;
	}
	while(1)
	{
		cc=getchar();
		if(cc>=48&&cc<=57)
		{
			s=s*10+cc-48;
		}
		else
		{
			break;
		}
	}
	if(f==true)
	{
		s=-s;
	}
	return s;
}
struct t1
{
	int u,v,l,r;
	long long sum;
	int tu,tv;
}t[1200005];
struct q1
{
	long long id,u,v;
}q[300005];
long long S(long long x,long long l)
{
	return (x+x+l-1)*l/2;
}
void spread(long long p)
{
	if(t[p].l!=t[p].r)
	{
		if(t[p].tu!=0)
		{
			t[p*2].tu=t[p*2+1].tu=t[p].tu;
			t[p*2].u=t[p*2].tu;
			t[p*2+1].u=t[p*2+1].tu;
		} 
		if(t[p].tv!=0)
		{
			t[p*2].tv=t[p*2+1].tv=t[p].tv;
			t[p*2].v=t[p*2].tv;
			t[p*2+1].v=t[p*2+1].tv;
		}
		if(t[p*2].u!=0&&t[p*2].v!=0) t[p*2].sum=v[t[p*2].u]*S(t[p*2].v-t[p*2].r,t[p*2].r-t[p*2].l+1);
		if(t[p*2+1].u!=0&&t[p*2+1].v!=0) t[p*2+1].sum=v[t[p*2+1].u]*S(t[p*2+1].v-t[p*2+1].r,t[p*2+1].r-t[p*2+1].l+1);
	}
	t[p].tu=t[p].tv=0;
}
void build(long long p,long long l,long long r)
{
	t[p].l=l;
	t[p].r=r;
	if(l==r)
	{
		t[p].u=L[l];
		t[p].v=R[l];
		t[p].sum=(R[l]-l)*v[t[p].u];
		return;
	}
	long long mid=(l+r)>>1;
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
	t[p].sum=t[p*2].sum+t[p*2+1].sum;
}
long long ask(long long p,long long l,long long r)
{
	if(l<=t[p].l&&r>=t[p].r)
	{
		return t[p].sum;
	}
	spread(p);
	long long ans=0;
	long long mid=(t[p].l+t[p].r)>>1;
	if(l<=mid)
	{
		ans=ans+ask(p*2,l,r);
	}
	if(r>mid)
	{
		ans=ans+ask(p*2+1,l,r);
	}
	return ans;
}
void changeL(long long p,long long l,long long r,long long va)
{
	spread(p);
	if(l<=t[p].l&&r>=t[p].r)
	{
		t[p].u=va;
		t[p].tu=va;
		if(t[p].u!=0&&t[p].v!=0) t[p].sum=v[t[p].u]*S(t[p].v-t[p].r,t[p].r-t[p].l+1);
		return;
	}
	long long mid=(t[p].l+t[p].r)>>1;
	if(l<=mid)
	{
		changeL(p*2,l,r,va);
	}
	if(r>mid)
	{
		changeL(p*2+1,l,r,va);
	}
	t[p].sum=t[p*2].sum+t[p*2+1].sum;
}
void changeR(long long p,long long l,long long r,long long va)
{
	spread(p);
	if(l<=t[p].l&&r>=t[p].r)
	{
		t[p].v=va;
		t[p].tv=va;
		if(t[p].u!=0&&t[p].v!=0) t[p].sum=v[t[p].u]*S(t[p].v-t[p].r,t[p].r-t[p].l+1);
		return;
	}
	long long mid=(t[p].l+t[p].r)>>1;
	if(l<=mid)
	{
		changeR(p*2,l,r,va);
	}
	if(r>mid)
	{
		changeR(p*2+1,l,r,va);
	}
	t[p].sum=t[p*2].sum+t[p*2+1].sum;
}
void del(long long x)
{
	changeL(1,he[x]+1,ne[x]-1,he[x]);
	changeR(1,he[x]+1,ne[x]-1,ne[x]);
	ne[he[x]]=ne[x];
	he[ne[x]]=he[x];
}
int main()
{
	long long n,m,Q;
	cin>>n>>m>>Q;
	for(long long i=1;i<=m;i++)
	{
		x[i]=read1();
	}
	for(long long i=1;i<=m;i++)
	{
		long long va=read1();
		v[x[i]]=va;
	}
	for(long long i=1;i<=Q;i++)
	{
		q[i].id=read1();
		q[i].u=read1();
		q[i].v=read1();
		if(q[i].id==1)
		{
			v[q[i].u]=q[i].v;
		}
	}
	long long p=1;
	L[1]=1;
	for(long long i=2;i<=n;i++)
	{
		if(v[i]>0)
		{
			he[i]=p;
			p=i;
		}
		L[i]=p;
	}
	p=n;
	R[n]=n;
	for(long long i=n-1;i>=1;i--)
	{
		if(v[i]>0)
		{
			ne[i]=p;
			p=i;
		}
		R[i]=p;
	}
	build(1,1,n);
	for(long long i=Q;i>=1;i--)
	{
		if(q[i].id==1)
		{
			del(q[i].u);
		}
		else
		{
			ans[i]=ask(1,q[i].u,q[i].v);
		}
	}
	for(long long i=1;i<=Q;i++)
	{
		if(q[i].id==2)
		{
			printf("%lld\n",ans[i]);
		}
	}
	return 0;
}
/*
8 3 1
1 3 8
3 24 10
2 2 5
*/