Ynoi入门题80pts求优化/卡常
查看原帖
Ynoi入门题80pts求优化/卡常
775993
codwarm楼主2024/4/18 22:15
// Problem: P9994 [Ynoi Easy Round 2024] TEST_132
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P9994
// Memory Limit: 512 MB
// Time Limit: 12000 ms
// Author: Eason
// Date:2024-04-18 20:08:26
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 0x3f3f3f3f
#define re register
#define PII pair<int,int>

static char buf[100000],*p1=buf,*p2=buf;
#define gc p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
inline int read() {int res=0,w=0; char c=gc; while (!isdigit(c)) w|=c=='-',c=gc; while (isdigit(c)) res=(res<<1)+(res<<3)+(c^48),c=gc; if (w) res=-res; return res;}
inline void write(ll x) {static int sta[50],top=0; if (x<0) putchar('-'),x=-x; do {sta[top++]=x%10,x/=10;}while (x); while (top) putchar(sta[--top]+48); putchar('\n');}

const int N = 1e6+5,mod = 1e9+7;
const int P = 1e9+7;

template <typename T>
void add(T &x, T y) { (x + y >= P ? x -= P - y : x += y); }
template <typename T>
void sub(T &x, T y) { (x - y > 0 ? x -= y : (x -= y) += P); }

int n,m;
struct node
{
	int x,y;
	ll v;
}a[N];
vector<int> v[N],v2[N];

int tag[N];
ll sum[N];

ll ksm(ll a,ll b)
{
	b %= (mod-1);
	ll res = 1;
	while (b)
	{
		if (b & 1) res = res * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return res;
}
unordered_map<int,bool> mpx,mpy;
signed main()
{
	n = read(),m = read();
	for (re int i = 1;i <= n;i++) 
		a[i] = {read(),read(),read()};
	for (re int i = 1;i <= n;i++)
	{
		v[a[i].x].push_back(i);
		v2[a[i].y].push_back(i);
		add(sum[a[i].y],a[i].v);
		//(sum[a[i].y] += a[i].v) %= mod;
	}
	const int S = 5000;
	while (m--)
	{
		int op = read(),x = read();
		if (op == 1)
		{
			if (v[x].size()<=S)
			{
				for (auto i : v[x]) 
				{
					//sum[a[i].y] = add(sum[a[i].y],(sub((a[i].v * a[i].v) % mod,a[i].v)));
					ll tp = a[i].v * a[i].v % mod;
					sub(tp,a[i].v);
					add(sum[a[i].y],tp);
					a[i].v *= a[i].v,a[i].v %= mod;
				}
			}
			else tag[x]++;
		}
		else
		{
			ll res = sum[x];
			for (auto i : v2[x])
			{
				if (tag[a[i].x])
				{
					sub(res,a[i].v);
					//res = (res -a[i].v + mod)%mod;
					add(res,ksm(a[i].v,(1<<tag[a[i].x])));
					//(res += ) %= mod;
				}
			}
			write(res);
		}
	}
	return 0;
}
2024/4/18 22:15
加载中...