题解 P9994

dead_X · 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;
}