题解怎么都是用暴力日过去的啊。
思路
考虑根号分治，设阈值为 \(B\)。
对于第二维出现次数超过 \(B\) 的，我们可以在修改时暴力更改，这部分复杂度为 \(O(\frac{nm}{B})\)。
对于第二维出现次数小于 \(B\) 的，我们可以在修改是打标记，查询时遍历一遍，这部分的复杂度为 \(O(mb)\)。
大多数题解对出现次数小于 \(B\) 的处理都没有达到严格的线性，而是使用了快速幂进行计算，这里给一种线性做法。
对于所有的数，我们把他们的离散对数算出来，在模 \(1000000007\) 意义下就是算 \(\log_5\)。
那么我们可以预处理 \(5\) 的光速幂，在查询的时候可以 \(O(1)\) 计算答案。
而在修改时，对原数平方相当于对离散对数乘二。
同样可以预处理二的次幂来做到。
问题就变成了在最开始计算每个数的离散对数。
首先可以使用 BSGS，我们预处理前 \(5\times 10^6\) 次方项，每次查询就只需要遍历 \(\frac{mod}{5\times 10^6}\) 约 \(200\) 下。
这样在复杂度上就已经非常优越了。
但在实现上，由于 BSGS 与哈希表（即使是手写哈希表）常数过大。
所以跑 \(10^6\) 次 BSGS 是非常慢的。
甚至表现的结果不如快速幂（当然这也与数据有关）。
怎么办呢。
考虑一种 BSGS 次数更少的方法。
对 \(mod\) 作带余除法 \(mod=ax+b(a,b\in Z,0\le b<x)\)，有：
于是可以得到：
若我们已经预处理出 \(≤ \sqrt{mod}\) 范围内的所有数的离散对数，那么只需考虑 \(x > \sqrt{mod}\) 的情况。
此时 \(a = \frac{mod}{x} < \sqrt{mod}\)，因此 \(a\), \(a + 1\) 的离散对数也是已知的。
于是，我们可以根据上面两条式子，将计算 \(\log x\) 的问题递归到计算 \(\log b\) 或 \(\log(x - b)\) 的问题。
由于 \(\min(b, x - b) \le \frac{x}{2}\)，就可以在 \(O(\log x)\) 的时间内计算 \(x\) 的离散对数。
我们也只需要执行 \(\sqrt{mod}\) 次 BSGS 算出前根号项即可。
这样常数大大减少，就可以完全不卡常的过了。
所以正解怎么可能会卡常呢。
Code
阈值 \(B\) 设为 \(500\)（因为光速幂非常龟速）。
这是完全没卡常的代码，在总时间可能没有快速幂快。
但最慢点只要 \(3s\)。
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define eb(...) emplace_back(__VA_ARGS__)
#define fro(i, x, y) for(int i = (x);i <= (y);i++)
#define pre(i, x, y) for(int i = (x);i >= (y);i--)
typedef int64_t i64;
typedef pair<int, int> PII;
const int B = 500;
const int D = 5e6;
const int P = 4e4;
const int I = 131072;
const int M = 2935019;
const int N = 1e6 + 10;
const int G = 5e6 + 10;
const int mod = 1e9 + 7;
const int phi = 1e9 + 6;
const int lgf = 5e8 + 3;
int n, m;
int sum[N], tag[N], ton[N];
int a[N], b[N], v[N], g[N], d[N];
vector<PII> big[N], sml[N];
i64 inv, pw1[N], pw2[N], pw3[N];
struct HashMap
{
int cnt, head[M];
struct edge { int to, val, nxt; } e[G];
inline int &operator[](const int &tmp)
{
int x = tmp % M;
for(int i = head[x]; i; i = e[i].nxt)
if(e[i].to == tmp) return e[i].val;
e[++cnt] = {tmp, 0, head[x]}, head[x] = cnt;
return e[cnt].val;
}
inline bool find(const int &tmp)
{
int x = tmp % M;
for(int i = head[x]; i; i = e[i].nxt)
if(e[i].to == tmp) return 1;
return 0;
}
} mp;
inline i64 power(int x)
{ return pw1[x&(I-1)] * pw2[x>>17] % mod; }
inline i64 power(i64 x, i64 y)
{
i64 res = 1;
while(y)
{
if(y & 1) res = res * x % mod;
x = x * x % mod, y /= 2;
}
return res;
}
inline void init()
{
pw1[0] = pw2[0] = pw3[0] = 1; i64 pw = 1;
fro(i, 1, I) pw1[i] = pw1[i - 1] * 5 % mod;
fro(i, 1, I) pw2[i] = pw2[i - 1] * pw1[I] % mod;
fro(i, 1, N - 10) pw3[i] = pw3[i - 1] * 2 % phi;
fro(i, 0, D) mp[pw] = i, pw = pw * 5 % mod;
inv = power(power(D), mod - 2);
auto ask = [&](int x) {
fro(i, 0, 200)
{
if(mp.find(x))
return i * D + mp[x];
x = x * inv % mod;
}
return -1;
};
fro(i, 1, P) d[i] = (i % 5 == 0 ? d[i / 5] + 1 : ask(i));
}
inline void add(int &x, int y, int M = mod)
{ x = (x + y >= M ? x + y - M : x + y); }
inline int Add(int x, int y)
{ return (x + y >= phi ? x + y - phi : x + y); }
inline int ask(int x)
{
if(x <= P) return d[x];
int q = mod / x, r = mod % x;
if(r < x - r)
return Add(Add(lgf, ask(r)), phi - d[q]);
return Add(ask(x - r), phi - d[q + 1]);
}
inline void solve()
{
cin >> n >> m, init();
fro(i, 1, n) cin >> a[i] >> b[i] >> v[i];
fro(i, 1, n) g[i] = ask(v[i]);
fro(i, 1, n) ton[b[i]]++;
fro(i, 1, n)
{
if(ton[b[i]] <= B) sml[b[i]].eb(a[i], g[i]);
if(ton[b[i]] > B) big[a[i]].eb(b[i], v[i]), add(sum[b[i]], v[i]);
}
fro(i, 1, m)
{
int op, x;
cin >> op >> x;
if(op == 1)
{
for(auto &[a, b] : big[x])
{
add(sum[a], mod - b);
b = 1ll * b * b % mod;
add(sum[a], b);
}
tag[x]++;
}
else
{
if(ton[x] > B)
cout << sum[x] << "\n";
else
{
int res = 0;
for(auto [a, b] : sml[x])
{
int pos = b * pw3[tag[a]] % phi;
add(res, power(pos));
}
cout << res << "\n";
}
}
}
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0);
solve();
return 0;
}