[SDOI 2019] 快速查询

Vijos 2051

把所有单独进行1操作的位置用std::unordered_map维护一下,另外把所有std::unordered_map里的元素之和和其他元素之和维护一下即可

#include <iostream>
#include <cstdio>
#include <unordered_map>

const int P = 1e7 + 19;

struct Data{
    int x, y, opt;
}a[100010];

int n, q, t, ans, tag0, tag1, tag2, sum, tot, inv[P];
std::unordered_map<int, int> val;

int ksm(int x, int y){
    int z = 1;
    for(; y; y >>= 1, x = 1ll * x * x % P)
        if(y & 1) z = 1ll * x * z % P;
    return z;
}

void work(Data w){
    int tmp;
    if(w.opt == 1){
        if(!val.count(w.x)) sum = ((sum - 1ll * tag1 * tag0 % P) % P - tag2) % P;
        else sum = ((sum - 1ll * val[w.x] * tag1 % P) % P - tag2) % P;
        val[w.x] = 1ll * (w.y - tag2) % P * inv[tag1] % P;
        sum = (sum + w.y) % P;
    }
    if(w.opt == 2){
        tag2 = (tag2 + w.x) % P;
        sum = (sum + 1ll * w.x * n % P) % P;
    }
    if(w.opt == 3){
        tag1 = 1ll * tag1 * w.x % P;
        tag2 = 1ll * tag2 * w.x % P;
        sum = 1ll * sum * w.x % P;
    }
    if(w.opt == 4){
        tag0 = w.x, tag1 = 1, tag2 = 0, sum = 1ll * n * tag0 % P;
        val.clear();
    }
    if(w.opt == 5){
        if(!val.count(w.x)) tmp = tag0;
        else tmp = val[w.x];
        tmp = (1ll * tmp * tag1 % P + tag2) % P;
        ans = (ans + tmp) % P;
    }
    if(w.opt == 6){
        ans = (ans + sum) % P;
    }
}

int main(){
    inv[1] = 1;
    for(int i = 2; i < P; i++) inv[i] = 1ll * (P - P / i) * inv[P % i] % P;
    scanf("%d%d", &n, &q);
    for(int i = 1; i <= q; i++){
        scanf("%d", &a[i].opt);
        if(a[i].opt <= 5) scanf("%d", &a[i].x);
        if(a[i].opt == 1) scanf("%d", &a[i].y);
        if(2 <= a[i].opt && a[i].opt <= 4)
            a[i].x = (a[i].x % P + P) % P;
        if(1 == a[i].opt)
            a[i].y = (a[i].y % P + P) % P;
    }
    tag1 = 1, tot = n;
    scanf("%d", &t);
    while(t--){
        int x, y;
        scanf("%d%d", &x, &y);
        for(int j = 1; j <= q; j++)
            work(a[(x + 1ll*y*j%q) % q + 1]);
    }
    printf("%d\n", (ans + P) % P);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注