LOJ #3110 「SDOI2019」快速查询题解

xiaoh 2020-5-26

题意

有一个长度为 $n$ 的序列( $1\leq n\leq 10^9$ ),接下来有 $q$ 个基础操作( $1\leq q\leq 10^5$ ),操作为以下六种之一 $:$

$1.$ 单点修改.

$2.$ 全局加

$3.$ 全局乘

$4.$ 全局赋值

$5.$ 单点查询

$6.$ 全局和查询

有 $t$ 组各 $q$ 个操作组合( $1\leq t\leq 100$ ),请输出所有查询结果之和对 $10^7+19$ 取模的结果.

题解

~~这么明显的操作，考虑平衡树~~

首先看到奇奇怪怪的询问次数就可以确定平衡树不可行,对于每个询问必须做到常数的时间回答.看到了大量的全局操作,而单点操作数量有限,且位置至多有 $q$ 个,因此考虑坐标离散化后全局处理.然后对于 $2,3$ 操作,直接维护 $add$ 和 $mul$ 两个 $tag$ ,分别对标记操作即可.对于 $1$ 操作,将对应位置上的数改成 $(val-add)\times inv_{mul}$ 即可.接下来碰到了一个比较棘手的 $4$ 操作.区间推平无法粗暴的还原数组,因此我们考虑维护一个更新时间的标记,记 $latest$ 为最近一次全局推平,则每次单点查询时检查一下这个点的更新时间和推平时间比那个晚,取晚的值进行操作即可.接下来要注意的是 $1$ 操作的逆元,鉴于模数不大,我们粗暴的计算每一个逆元即可.( $LOJ$ 的评测机较快,可以直接暴力快速幂计算,但是在你谷上就要用稍微快一点的计算方法了？).时间复杂度 $O(tq+q\log q+mod\log mod)$ .

Code

#include<bits/stdc++.h>
#define mod 10000019
using namespace std;
template<typename T>
inline void read(T &x)
{
	x=0;
	int f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') f=-1;
		ch=getchar();
}
	while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
	x*=f;
	return;
}	
template<typename T>
void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>=10) write(x/10);
	putchar(x%10+'0');
	return;
}
const int MAXN=1000000010,MAXQ=100010,MAXT=110;
int n,q,t;
struct node{
    int op,pos;
    long long val;
}a[MAXQ];
int tot=0;
int b[MAXQ];
map<int,int> mp;
inline void prework()
{
    sort(b+1,b+tot+1);
    int cnt=0;
    for(register int i=1;i<=tot;++i) 
    if(!mp[b[i]]) mp[b[i]]=++cnt;
    for(register int i=1;i<=q;++i)
    if(a[i].op==1||a[i].op==5) a[i].pos=mp[a[i].pos];
}
int f[MAXQ];
inline int pow_mod(register int a,register int b)
{
    if(b==0) return 1;
    if(b==1) return a;
    register int x=pow_mod(a,b>>1);
    x=(int)(1ll*x*x%mod);
    if(b&1) x=(int)(1ll*x*a%mod);
    return x;
}
int inv[mod];
int g[MAXQ];
int main()
{
    for(register int i=1;i<mod;++i) inv[i]=pow_mod(i,mod-2);
    register long long tag1=1,tag2=0;
    register long long ans=0,sum=0;
    register int latest=0;
    read(n),read(q);
    for(register int i=1;i<=q;++i)
    {
        read(a[i].op);
        switch(a[i].op)
        {
            case 1:read(a[i].pos),read(a[i].val),b[++tot]=a[i].pos;break;
            case 2:read(a[i].val);break;
            case 3:read(a[i].val);break;
            case 4:read(a[i].val);break;
            case 5:read(a[i].pos),b[++tot]=a[i].pos;break;
            case 6:break;
        }
    }
    prework();
    read(t);
    for(register int i=1;i<=t;++i)
    {
        int u,v;
        read(u),read(v);
        for(register int tmp=1,j=(u+v)%q;tmp<=q;++tmp,j=(j+v)%q)
        {
            register int op=a[j+1].op,pos=a[j+1].pos;
            register long long val=a[j+1].val;
            if(op==1)
            {
                if(g[pos]>=latest) ans=(ans-f[pos]*tag1-tag2)%mod;
                else ans=(ans-tag2)%mod;
                f[pos]=(int)((val-tag2)*inv[(tag1+mod)%mod]%mod),g[pos]=(i-1)*q+tmp,ans+=val,ans%=mod;
            }
            else if(op==2) tag2+=val,tag2%=mod,ans+=val*n,ans%=mod;
            else if(op==3) tag1*=val,tag1%=mod,tag2*=val,tag2%=mod,ans*=val,ans%=mod;
            else if(op==4) tag1=1,tag2=val,ans=val*n%mod,latest=(i-1)*q+tmp;
            else if(op==5)
            {
                if(g[pos]>=latest) sum=(sum+f[pos]*tag1+tag2)%mod;
                else sum=(sum+tag2)%mod;
            }
            else sum=(sum+ans)%mod;
        }
    }
    write((sum%mod+mod)%mod),putchar('\n');
	return 0;
}