自动搬运

查看原文

来自洛谷，原作者为

	dead_X Still we rise

搬运于2025-08-24 22:53:45，当前版本为作者最后更新于2024-01-25 16:19:57，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前言

咋大家都不是单根？

思路

看着就不太能 $\text{polylog}$，考虑阈值分治。

那么对于一个点数 $<B$ 的行可以暴力做，时间复杂度 $O(mB)$。

对于点数 $\geq B$ 的行，每行单独扫一遍所有询问，就可以知道对应列的贡献是 $v_i^{2^t}$，共有 $\frac{nm}{B}$ 个贡献。

接下来是如何计算 $v_i^{2^t}\bmod p$，费马小定理告诉我们这等于 $v_i^{2^t\bmod (p-1)}\bmod p$，但是这样快速幂还是 $O(\log p)$ 的。

考虑到一共只有 $n$ 个数，可以使用光速幂，预处理 $v_i$ 的 $2^8,2^{16},2^{24}$ 次幂的值，就可以做到 $O(p^{\epsilon})-O(1)$ 了。

总时间复杂度 $O(mB+\frac{nm}{B}+np^{\epsilon})$，取 $B=\sqrt n$ 可以做到 $O(m\sqrt n+np^{\epsilon})$。

代码

// 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
// 
// Powered by CP Editor (https://cpeditor.org)

//泥の分際で私だけの大切を奪おうだなん
#include<bits/stdc++.h>
using namespace std;
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
const int p=1e9+7,q=1e9+6,B=2000;
struct multi
{
	int a0[256],a1[256],a2[256],a3[256];
	void init(int b)
	{
		a0[0]=a1[0]=a2[0]=a3[0]=1;
		for(int i=1; i<256; ++i) a0[i]=1ll*a0[i-1]*b%p;
		b=1ll*b*a0[255]%p;
		for(int i=1; i<256; ++i) a1[i]=1ll*a1[i-1]*b%p;
		b=1ll*b*a1[255]%p;
		for(int i=1; i<256; ++i) a2[i]=1ll*a2[i-1]*b%p;
		b=1ll*b*a2[255]%p;
		for(int i=1; i<256; ++i) a3[i]=1ll*a3[i-1]*b%p;
	}
	int qp(int x)
	{return 1ll*a3[x>>24]*a2[(x>>16)&255]%p
	*a1[(x>>8)&255]%p*a0[x&255]%p;}
}Z;
int x[1000003],y[1000003],z[1000003];
int tx[1000003],sy[1000003],ans[1000003];
vector<int> vx[1000003],qu[1000003];
int op[1000003],v[1000003],pre[1000003];
int pw[1000003];
signed main()
{
	int n=read(),m=read();
	pw[0]=1;
	for(int i=1; i<=m; ++i) pw[i]=(pw[i-1]<<1)%q;
	for(int i=1; i<=n; ++i)
		x[i]=read(),y[i]=read(),z[i]=read(),
		vx[x[i]].push_back(i);
	for(int i=1; i<=m; ++i)
	{
		op[i]=read(),v[i]=read();
		if(op[i]==2) qu[v[i]].push_back(i);
	}
	for(int i=1; i<=n; ++i)
		if((int)vx[i].size()>=B)
		{
			for(int j=1; j<=m; ++j)
				pre[j]=(pre[j-1]+(op[j]==1&&v[j]==i));
			for(int j:vx[i])
			{
				Z.init(z[j]);
				for(int k:qu[y[j]])
					ans[k]=(ans[k]+Z.qp(pw[pre[k]]))%p;
			}
		}
		else for(int j:vx[i])
			sy[y[j]]=(sy[y[j]]+z[j])%p;
	for(int i=1; i<=m; ++i)
		if(op[i]==2) printf("%d\n",(ans[i]+sy[v[i]])%p);
		else if(vx[v[i]].size()<B)
			for(int j:vx[v[i]])
				sy[y[j]]=(sy[y[j]]+p-z[j])%p,
				z[j]=1ll*z[j]*z[j]%p,
				sy[y[j]]=(sy[y[j]]+z[j])%p;
	return 0;
}