题解 CF1207F 【Remainder Problem】

发表于 更新于 阅读次数： Waline：
CF1207F 【Remainder Problem】题解。

这个题其实有原题的……参见P3396

看到$500000$的数据范围想必大家也有感觉，$O(n^2)$的暴力可以不用考虑了……要是您能n方过百万那么当我没说

然而我们又是对每次%一个数之后的一些数进行操作，所以线段树/树状数组也不太好维护

您能写出来那是我太弱，Orz

有没有什么方法能快速解决这些关于%的问题的呢？

联想到分块，分块的本质就是对于每个数%之后放进相对应的块中，然后大的直接统计，小的直接暴力。而且$O(\sqrt{n})$的算法复杂度，也是可以承受的。

那么我们就可以采用基于分块的思想解决这个问题了。

于是代码就呼之欲出了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <bits/stdc++.h>
using namespace std;
int m,opt,x,y;
#define ll long long
ll ans[710][710],a[500005];
const int n=500000;
struct control
{
    int ct,val;
    control(int Ct,int Val=-1):ct(Ct),val(Val){}
    inline control operator()(int Val)
    {
        return control(ct,Val);
    }
}_endl(0),_prs(1),_setprecision(2);
struct FastIO
{
    #define IOSIZE 1000000
    char in[IOSIZE],*p,*pp,out[IOSIZE],*q,*qq,ch[20],*t,b,K,prs;
    FastIO():p(in),pp(in),q(out),qq(out+IOSIZE),t(ch),b(1),K(6){}
    ~FastIO(){fwrite(out,1,q-out,stdout);}
    inline char getch()
    {
        return p==pp&&(pp=(p=in)+fread(in,1,IOSIZE,stdin),p==pp)?b=0,EOF:*p++;
    }
    inline void putch(char x)
    {
        q==qq&&(fwrite(out,1,q-out,stdout),q=out),*q++=x;
    }
    inline void puts(const char str[]){fwrite(out,1,q-out,stdout),fwrite(str,1,strlen(str),stdout),q=out;}
    inline void getline(string& s)
    {
        s="";
        for(register char ch;(ch=getch())!='\n'&&b;)s+=ch;
    }
    #define indef(T) inline FastIO& operator>>(T& x)\
    {\
        x=0;register char f=0,ch;\
        while(!isdigit(ch=getch())&&b)f|=ch=='-';\
        while(isdigit(ch))x=(x<<1)+(x<<3)+(ch^48),ch=getch();\
        return x=f?-x:x,*this;\
    }
    indef(int)
    indef(long long)
    inline FastIO& operator>>(char& ch){return ch=getch(),*this;}
    inline FastIO& operator>>(string& s)
    {
        s="";register char ch;
        while(isspace(ch=getch())&&b);
        while(!isspace(ch)&&b)s+=ch,ch=getch();
        return *this;
    }
    inline FastIO& operator>>(double& x)
    {
        x=0;register char f=0,ch;
        double d=0.1;
        while(!isdigit(ch=getch())&&b)f|=(ch=='-');
        while(isdigit(ch))x=x*10+(ch^48),ch=getch();
        if(ch=='.')while(isdigit(ch=getch()))x+=d*(ch^48),d*=0.1;
        return x=f?-x:x,*this;
    }
    #define outdef(_T) inline FastIO& operator<<(_T x)\
    {\
        !x&&(putch('0'),0),x<0&&(putch('-'),x=-x);\
        while(x)*t++=x%10+48,x/=10;\
        while(t!=ch)*q++=*--t;\
        return *this;\
    }
    outdef(int)
    outdef(long long)
    inline FastIO& operator<<(char ch){return putch(ch),*this;}
    inline FastIO& operator<<(const char str[]){return puts(str),*this;}
    inline FastIO& operator<<(const string& s){return puts(s.c_str()),*this;}
    inline FastIO& operator<<(double x)
    {
        register int k=0;
        this->operator<<(int(x));
        putch('.');
        x-=int(x);
        prs&&(x+=5*pow(10,-K-1));
        while(k<K)putch(int(x*=10)^48),x-=int(x),++k;
        return *this;
    }
    inline FastIO& operator<<(const control& cl)
    {
        switch(cl.ct)
        {
            case 0:putch('\n');break;
            case 1:prs=cl.val;break;
            case 2:K=cl.val;break;
        }
    }
    inline operator bool(){return b;}
}io;
int main(){
    io>>m;
    int sz=sqrt(n);//每个块的大小
    while (m--){
        io>>opt>>x>>y;
        if (opt==2){
            if (x<=sz)io<<ans[x][y]<<"\n";//可以直接进行的查询操作，直接输出
            else{
                ll sum=0;
                for (int i=y;i<=n;i+=x)sum+=a[i];
                io<<sum<<"\n";//否则暴力解决
            }
        }
        else if (opt==1){
            for (int p=1;p<=sz;p++)ans[p][x%p]+=y;//把修改x会产生影响的块的值都更新
            a[x]+=y;//然后更新原数组
        }
    }
}