题目链接
(Solution:)
容易看出是一道平衡树的题(这里我们用(fhq-Treap)维护)
但是由于(A)操作是全局修改,所以我们甚至不需要维护一个延迟标记,只需在全局记录两个标记即可
(Code:)
#include<bits/stdc .h>
using namespace std;
namespace my_std
{
typedef long long ll;
#define fr(i,x,y) for(ll i=(x);i<=(y);i )
inline ll read()
{
ll sum=0,f=1;
char ch=0;
while(!isdigit(ch))
{
if(ch=='-') f=-1;
ch=getchar();
}
while(isdigit(ch))
{
sum=(sum<<1) (sum<<3) (ch^48);
ch=getchar();
}
return sum*f;
}
inline void write(ll x)
{
if(x<0)
{
putchar('-');
x=-x;
}
if(x>9) write(x/10);
putchar(x '0');
}
}
using namespace my_std;
const ll N=5e5 50;
ll n,m,rt,cnt,sum,tg1,tg2=1;
char opt[10];
struct node
{
ll l,r,key,v,val,sz;
}fhq[N];
inline void pushup(ll p)
{
fhq[p].sz=fhq[fhq[p].l].sz fhq[fhq[p].r].sz 1;
}
inline ll newnode(ll val,ll v)
{
cnt ;
fhq[cnt].val=val;
fhq[cnt].v=v;
fhq[cnt].key=rand();
fhq[cnt].sz=1;
return cnt;
}
void split(ll p,ll k,ll &x,ll &y)
{
if(!p)
{
x=y=0;
return;
}
if(fhq[p].val<=k)
{
x=p;
split(fhq[p].r,k,fhq[p].r,y);
}
else
{
y=p;
split(fhq[p].l,k,x,fhq[p].l);
}
pushup(p);
}
ll merge(ll a,ll b)
{
if(!a||!b) return a b;
if(fhq[a].key<fhq[b].key)
{
fhq[a].r=merge(fhq[a].r,b);
pushup(a);
return a;
}
else
{
fhq[b].l=merge(a,fhq[b].l);
pushup(b);
return b;
}
}
inline int find(ll val)
{
ll x,y,z;
split(rt,val-1,x,y);
split(y,val,y,z);
rt=merge(merge(x,y),z);
return (y!=0);
}
inline void update(ll p,ll q)
{
if(find(p))
{
ll x,y,z;
split(rt,p-1,x,y);
split(y,p,y,z);
sum-=fhq[y].v;
sum =q;
fhq[y].v=q;
rt=merge(merge(x,y),z);
}
else
{
ll x,y;
split(rt,p,x,y);
sum-=(ll)p*tg2 tg1;
sum =q;
rt=merge(merge(x,newnode(p,q)),y);
}
}
int main(void)
{
n=read(),m=read();
sum=n*(n 1)/2;
fr(i,1,m)
{
scanf("%s",opt);
if(opt[0]=='A')
{
ll p,q;
p=read(),q=read();
tg2=p,tg1=q;
sum=(n*(n 1)/2)*p q*n;
rt=0;
}
else
{
ll x,y;
x=read(),y=read();
update(x,y);
}
write(sum);
putchar('n');
}
return 0;
}