96pts 求卡常 qwq
查看原帖
96pts 求卡常 qwq
879904
WorldMachine楼主2024/11/4 20:59
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
namespace fast_IO{
	#define FASTIO
	#define IOSIZE (1 << 20)
	char ibuf[IOSIZE],obuf[IOSIZE];char*p1=ibuf,*p2=ibuf,*p3=obuf;
	#ifdef ONLINE_JUDGE
	#define getchar()((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
	#define putchar(x)((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
	#endif
	#define isdigit(ch)(ch>47&&ch<58)
	#define isspace(ch)(ch<33)
	template<typename T>inline T read(){T s=0;int w=1;char ch;while(ch=getchar(),!isdigit(ch)and(ch!=EOF))if(ch=='-')w=-1;if(ch==EOF)return false;while(isdigit(ch))s=s*10+ch-48,ch=getchar();return s*w;}template<typename T>inline bool read(T&s){s=0;int w=1;char ch;while(ch=getchar(),!isdigit(ch)and(ch!=EOF))if(ch=='-')w=-1;if(ch==EOF)return false;while(isdigit(ch))s=s*10+ch-48,ch=getchar();return s*=w,true;}inline bool read(char&s){while(s=getchar(),isspace(s));return true;}inline bool read(char*s){char ch;while(ch=getchar(),isspace(ch));if(ch==EOF)return false;while(!isspace(ch))*s++=ch,ch=getchar();*s='\000';return true;}template<typename T>inline void print(T x){if(x<0)putchar('-'),x=-x;if(x>9)print(x/10);putchar(x%10+48);}inline void print(char x){putchar(x);}inline void print(char*x){while(*x)putchar(*x++);}inline void print(const char*x){for(int i=0;x[i];i++)putchar(x[i]);}
	#ifdef _GLIBCXX_STRING
	inline bool read(std::string&s){s="";char ch;while(ch=getchar(),isspace(ch));if(ch==EOF)return false;while(!isspace(ch))s+=ch,ch=getchar();return true;}inline void print(std::string x){for(int i=0,n=x.size();i<n;i++)putchar(x[i]);}
	#endif
	template<typename T,typename...T1>inline int read(T&a,T1&...other){return read(a)+read(other...);}template<typename T,typename...T1>inline void print(T a,T1...other){print(a);print(other...);}struct Fast_IO{~Fast_IO(){fwrite(obuf,p3-obuf,1,stdout);}}qwq;template<typename T>Fast_IO&operator>>(Fast_IO&qwq,T&b){return read(b),qwq;}template<typename T>Fast_IO&operator<<(Fast_IO&qwq,T b){return print(b),qwq;}
}using namespace fast_IO;
namespace LOG {
	const int N = 50005;
	int qpow(int a, int b, int p) {
		int c = 1;
		while (b) {
			if (b & 1) c = (ll)c * a % p;
			a = (ll)a * a % p, b >>= 1;
		}
		return c;
	}
	gp_hash_table<int, int> mp;
	const int p = 1e9 + 7, g = 5, lim = 31623;
	int blk, w;
	void init(int g, int P, int B) {
		blk = B, w = qpow(qpow(g, blk, p), p - 2, p);
		int x = 1;
		for (int i = 0; i < blk; i++) mp[x] = i, x = (ll)x * g % p;
	}
	int BSGS(int a) {
		int x = a, tot = p / blk;
		for (int i = 0; i <= tot; i++) {
			if (mp.find(x) != mp.end()) return i * blk + mp[x];
			x = (ll)x * w % p;
		}
		return -1;
	}
	int lg_1, tot, pri[N], lg[N];
	bool vis[N];
	inline int mod(int x, int p) { return x >= p ? x - p : x; }
	void sieve(int n) {
		for (int i = 2; i <= n; i++) {
			if (!vis[i]) pri[++tot] = i, lg[i] = BSGS(i);
			for (int j = 1, k; j <= tot && i * pri[j] <= n; j++) {
				k = pri[j];
				vis[i * k] = 1, lg[i * k] = mod(lg[i] + lg[k], p - 1);
				if (!(i % k)) break;
			}
		}
	}
	int Log(int a) {
		if (a <= lim) return lg[a];
		int b = p / a, c = p % a;
		if (c < a - c) return mod(mod(lg_1 + Log(c), p - 1) - lg[b] + p - 1, p - 1);
		return mod(Log(a - c) - lg[b + 1] + p - 1, p - 1);
	}
	void init() {
		init(g, p, 1.2 * sqrt(p * sqrt(p) / log(p)));
		lg_1 = BSGS(p - 1);
		sieve(lim);
	}
}
using LOG::Log;
namespace POW {
	const int p = 1e9 + 7, B = 31630, g = 5;
	int p1[B], p2[B];
	void init() {
		p1[0] = p2[0] = 1;
		for (int i = 1; i < B; i++) p1[i] = (ll)p1[i - 1] * g % p;
		p2[1] = (ll)p1[B - 1] * g % p;
		for (int i = 2; i < B; i++) p2[i] = (ll)p2[i - 1] * p2[1] % p;
	}
	int Pow(int x) { return (ll)p2[x / B] * p1[x % B] % p; }
}
using POW::Pow;
const int N = 1.2e6 + 5, B = 5005, p = 1e9 + 7;
int n, m, b, l[N], r[N], tag[N], id[N], tot, big[B], sum[N];
bool flg[N];
gp_hash_table<int, int> pnt[B];
struct node { int x, y, v, l; } a[N];
inline bool cmp(const node &a, const node &b) { return a.x < b.x; }
inline int mod(int x, int y) { return x >= y ? x - y : x; }
int main() {
	LOG::init();
	POW::init();
	qwq >> n >> m;
	for (int i = 1; i <= n; i++) qwq >> a[i].x >> a[i].y >> a[i].v, a[i].l = Log(a[i].v);
	sort(a + 1, a + 1 + n, cmp);
	for (int i = 1; i <= n; i++) {
		if (a[i].x != a[i - 1].x) l[a[i].x] = i, r[a[i - 1].x] = i - 1;
	}
	r[a[n].x] = n;
	b = 0.8 * sqrt(n);
	for (int i = 1; i <= n; i++) {
		if (r[i] - l[i] + 1 > b) big[++tot] = i, tag[i] = flg[i] = 1, id[i] = tot;
	}
	for (int i = 1; i <= n; i++) {
		if (!flg[a[i].x]) sum[a[i].y] = mod(sum[a[i].y] + a[i].v, p);
		else pnt[id[a[i].x]][a[i].y] = a[i].l;
	}
	int op, x, y, ans;
	while (m--) {
		qwq >> op;
		if (op == 1) {
			qwq >> x;
			if (tag[x]) tag[x] = mod(tag[x] << 1, p - 1);
			else {
				for (int i = l[x]; i <= r[x]; i++) {
					sum[a[i].y] = (sum[a[i].y] - a[i].v + (ll)a[i].v * a[i].v) % p;
					a[i].v = (ll)a[i].v * a[i].v % p;
				}
			}
		} else {
			qwq >> y;
			ans = sum[y];
			for (int i = 1; i <= tot; i++) {
				if (pnt[i].find(y) != pnt[i].end()) ans = mod(ans + Pow((ll)pnt[i][y] * tag[big[i]] % (p - 1)), p);
			}
			qwq << ans << '\n';
		}
	}
}
2024/11/4 20:59
加载中...