LibreOJ 3110 「SDOI2019」快速查询

我也不知道是什么算法……
听说有人用 unordered_map 没过？我来为它证明！

首先，我们规定标记的顺序：加法 > 乘法 > 单点赋值 > 整体赋值。
然后，打标记的同时，注意一下其他标记的影响。

在单点赋值的时候需要逆元，线性递推相信人均了解（
同时，为了卡常，注意 unordered_map 访问的时候先用 count 判一下（直接访问会造成创建 0）。
以及全开 int。

代码：

#include <cstdio>
#include <algorithm>
#include <tr1/unordered_map>
using namespace std;
const int Q = 1e5;
const int T = 100;
const int mod = 1e7 + 19;
int n,q,t;
int inv[mod + 5];
int add,mul = 1,reset,sum,ans;
int a[T + 5],b[T + 5];
tr1::unordered_map<int,int> v;
struct note
{
    int op,x,val;
} chg[Q + 5];
int main()
{
    inv[1] = 1;
    for(register int i = 2;i < mod;++i)
        inv[i] = (long long)(mod - mod / i) * inv[mod % i] % mod;
    scanf("%d%d",&n,&q);
    for(register int i = 1;i <= q;++i)
    {
        scanf("%d",&chg[i].op);
        if(chg[i].op == 1)
            scanf("%d%d",&chg[i].x,&chg[i].val),chg[i].val = (chg[i].val % mod + mod) % mod;
        else if(chg[i].op == 5)
            scanf("%d",&chg[i].x);
        else if(chg[i].op ^ 6)
            scanf("%d",&chg[i].val),chg[i].val = (chg[i].val % mod + mod) % mod;
    }
    scanf("%d",&t);
    for(register int i = 1;i <= t;++i)
        scanf("%d%d",a + i,b + i),a[i] %= q,b[i] %= q;
    for(register int i = 1,num,op,x,val;i <= t;++i)
        for(register int j = 1;j <= q;++j)
        {
            num = (a[i] + (long long)j * b[i] % q) % q + 1;
            op = chg[num].op,x = chg[num].x,val = chg[num].val;
            if(op == 1)
            {
                if(v.count(x))
                    sum = ((sum - (long long)v[x] * mul % mod - add) % mod + mod) % mod;
                else
                    sum = ((sum - (long long)reset * mul % mod - add) % mod + mod) % mod;
                v[x] = (long long)(val - add + mod) % mod * inv[mul] % mod;
                sum = (sum + val) % mod;
            }
            else if(op == 2)
                add = (add + val) % mod,sum = (sum + (long long)n * val) % mod;
            else if(op == 3)
                add = (long long)add * val % mod,mul = (long long)mul * val % mod,sum = (long long)sum * val % mod;
            else if(op == 4)
                add = 0,mul = 1,reset = val,sum = (long long)n * val % mod,v.clear();
            else if(op == 5)
            {
                if(v.count(x))
                    ans = (ans + (long long)v[x] * mul % mod + add) % mod;
                else
                    ans = (ans + (long long)reset * mul % mod + add) % mod;
            }
            else
                ans = (ans + sum) % mod;
        }
    printf("%d\n",ans);
}