noi.ac #51 array 题解

$noi.ac$ #51 array题解

2020-2-13 xiaoh

题意

有一个长度为$n$的序列a($1\leq n\leq 5\times 10^7$)，初始情况下$a_i$的值为$i$，接下来有$m$个操作($1\leq m\leq 5\times 10^5$),每个操作可能为以下两个之一：
$A$:对于所有的$i\in [1,n]$，将$a_i$改为$p\times i+q$ ($|p|\leq 10^3,|q|\leq 10^9$);
$B$:将$a_x$改为$y$ ($|y|\leq 10^9$).
要求在每一次操作结束后输出 $\Sigma a$.

题解

由于$n$达到$10^7$级别，因此不可能暴力维护整个$a$序列。注意到修改为区间赋值和单点修改，所以考虑用数据结构维护"单点修改"修改过的元素。这样一来$A$操作就是清空整个数据结构并重新赋初值，$B$操作就是在数据结构上添加元素/修改，并将其计入总的$sum$中。所以我们的数据结构要实现动态插入，查询某个值是否存在，以及清空，且每个操作必须在 $\log$级别以内的时间内完成。不难想到平衡树可以完成上述操作(代码中平衡树的实现为fhq-Treap,即非旋Treap)。时间复杂度O(mlogn)，其中查询和添加为 $\log$级别的，清空$O(1)$。

Code

#include<bits/stdc++.h>
using namespace std;
const int MAXN=500010;
int tot=0;
int rt=0;
long long sum;
long long add=0,mul=1;
struct node{//fhq-Treap的代码部分注释就不赘述了，就是一个板子
    int l,r;
    int val,dat;
    long long val2;
    int sz;
}f[MAXN];
inline void pushup(int p)
{
    f[p].sz=f[f[p].l].sz+f[f[p].r].sz+1;
}
inline int New(int val,long long val2)
{
    tot++;
    f[tot].val=val,f[tot].val2=val2,f[tot].dat=rand();
    f[tot].sz=1;
    return tot;
}
void split(int p,int k,int &x,int &y)
{
    if(!p)
    {
        x=y=0;
        return;
    }
    if(f[p].val<=k)
    {
        x=p;
        split(f[p].r,k,f[p].r,y);
    }
    else
    {
        y=p;
        split(f[p].l,k,x,f[p].l);
    }
    pushup(p);
}
int merge(int a,int b)
{
    if(!a||!b) return a+b;
    if(f[a].dat<f[b].dat)
    {
        f[a].r=merge(f[a].r,b);
        pushup(a);
        return a;
    }
    else
    {
        f[b].l=merge(a,f[b].l);
        pushup(b);
        return b;
    }
}
inline bool find(int val)//查找值是否存在
{
    int x,y,z;
    split(rt,val-1,x,y);
    split(y,val,y,z);
    bool ret=(y!=0);
    rt=merge(merge(x,y),z);
    return ret;
}
inline void insert(int p,long long q)
{
    if(find(p))//若值存在则直接修改
    {
        int x,y,z;
        split(rt,p-1,x,y);
        split(y,p,y,z);
        sum-=f[y].val2;
        sum+=q;
        f[y].val2=q;
        rt=merge(merge(x,y),z);
    }
    else//否则插入这个值
    {
        int x,y;
        split(rt,p,x,y);
        sum-=(long long)p*mul+add;
        sum+=q;
        rt=merge(merge(x,New(p,q)),y);
    }
}
int n,m;
int main()
{
    scanf("%d%d",&n,&m);
    sum=(long long)n*(long long)(n+1)/(long long)2;
    for(register int i=1;i<=m;i++)
    {
        char op[10];
        scanf("%s",op);
        if(op[0]=='A')
        {
            long long p,q;
            scanf("%lld%lld",&p,&q);
            mul=p,add=q;
            sum=(long long)n*(long long)(n+1)/(long long)2;//修改总和
            sum=sum*p+q*(long long)n;
            rt=0;//清空fhq-Treap
        }
        else
        {
            int x;
            long long y;
            scanf("%d%lld",&x,&y);
            insert(x,y);//修改对应的值
        }
        printf("%lld\n",sum);
    }
}

后记

一开始读这道题读错了，把$A$操作硬生生读成了$a_i=p\times a_i+q$，然后看了看数据差点自爆，这个八成要高精，还要写pushdown,又懒得写高精，就直接套了long double……后来发现题读错的时候我已经在调样例了$QAQ$没办法，只能流着泪狂删代码+修改，结果因为long double常数太大居然又爆了一次，最终把long double全部换成long long之后才过……真是个悲伤的故事。