vijos2051 SDOI2019 快速查询

吐槽

竟然让\(nlog\)的做法卡过去了。。

思路

因为\(1 \le q \le 10^5\)，所以可以先对每个标准操作，所操作的位置进行重标号。这样所有的下标都是在\(10^5\)以内的。

乘和加操作都可以写成\(kx+b\)的形式。然后对于这些操作维护一个前缀。然后就可以得到一个区间内的操作了。

区间查询我们只要找个\(tot\)来维护一下当前的所有元素和，就行了。

单点查询，观察其上次赋值的时间。如果早于集体赋值，那么就输出当前大多数的值。

否则就将其上次赋的值乘上从上次赋值到当前时间点这个时间段内的操作。

代码

/*
* @author: wxyww
* @date:   2019-05-07 20:58:04
* @last modified time: 2019-05-11 10:33:03
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
#include<map>
using namespace std;
typedef long long ll;
const int n = 100010,mod = 1e7 + 19;
map<int,int>ma;
ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
struct node {
    int opt,pos,val;
}que[n];
int tot,s[n],a[n],b[n],now,inv[mod + 1],n,t,q,mul[n * 100],add[n * 100];
int lst[n],last;
int query(int x,int num) {
    if(lst[x] <= last) return now;
    int cheng = 1ll * mul[num] * inv[mul[lst[x]]] % mod;
    int jia = (add[num] - 1ll * add[lst[x] - 1] * cheng % mod + mod) % mod;
    return (1ll * s[x] * cheng % mod + jia) % mod;
}
int ans;
void solve(int x,int num) {
    int opt = que[x].opt,pos = que[x].pos,val = que[x].val % mod;
    mul[num] = mul[num - 1],add[num] = add[num - 1];
    if(opt == 1) {
        tot -= query(pos,num);
        tot += val;
        tot = (tot % mod + mod) % mod;
        lst[pos] = num;
        s[pos] = val;
    }
    else if(opt == 2) {
        tot += (1ll * n * val % mod + mod) % mod;
        tot = (tot % mod + mod) % mod;
        add[num] += val;
        add[num] = (add[num] %mod + mod) % mod;
        now += val;
        now = (now % mod + mod) % mod;
    }
    else if(opt == 3) {
        tot = (1ll * tot * val % mod + mod) % mod;
        now = (1ll * now * val % mod + mod) % mod;
        add[num] = (1ll * add[num] * val % mod + mod) % mod;
        mul[num] = (1ll * mul[num] * val % mod + mod) % mod;
    }
    else if(opt == 4) { 
        tot = (1ll * val * n % mod + mod) % mod;
        mul[num] = 1;add[num] = 0;
        now = val;
        last = num;
    }
    else if(opt == 5) ans += query(pos,num),ans = (ans % mod + mod) % mod;
    else ans = ((ans + tot) % mod + mod) % mod;
}
int main() {
    n = read(),q = read();
    for(int i = 1;i <= q;++i) {
        int opt = que[i].opt = read();
        if(opt == 1) {
            que[i].pos = read();que[i].val = read();
        }
        else if(opt == 6) continue;
        else if(opt == 5) que[i].pos = read();
        else que[i].val = read();
    }

    inv[1] = 1;
    for(int i =  2;i < mod;++i) inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;

    int js = 0;
    for(int i = 1;i <= q;++i) {
        if(!que[i].pos) continue;
        if(!ma[que[i].pos])     ma[que[i].pos] = ++js;
        que[i].pos = ma[que[i].pos];
    }

    int t = read(),num = 0;
    for(int i = 1;i <= t;++i) a[i] = read(),b[i] = read();
    for(int i = 1;i <= t;++i)
        for(int j = 1;j <= q;++j)
            solve((a[i] + 1ll * j * b[i] % q) % q + 1,++num);

    cout<<(ans % mod + mod) % mod;
    return 0;
}