(CF1580C)Train Maintenance

发表于

原题链接

思路:

根号分治

根据$x+y$的值将火车分为两类:

若$x+y \geq \sqrt{m}$, 此时最多只有$\sqrt{m}$段维修时间段, 使用差分存储这些火车的维修时间段, 随时间推进维护其前缀和.

若$x+y < \sqrt{m}$, 维护一个二维数组$a_{i,j}$, 表示有多少$x+y=i$列车在第$j+ki$天维护. 这样的空间复杂度是$O(\sqrt{m}^2) = O(m)$

这样便可以在$O(\sqrt{m})$的时间上修改和查询, 空间复杂度为$O(n+m)$

注意修改差分时维护的前缀和的修改.

代码:

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
#include <cstdio>
#include <cctype>
#include <cmath>
const int Mn(200500), Mm(200500), Ms(505);
template<typename T> void qrd(T& x) {
    x = 0;
    int c = getchar();
    while(!isdigit(c)) {
        c = getchar();
    }
    while(isdigit(c)) {
        x = x*10 + c - '0';
        c = getchar();
    }
}
template<typename T, typename... Ts> void qrd(T& x, Ts&... xs) {    //快读
    qrd(x); qrd(xs...);
}

struct Trn {    //火车
    int x, y;
}at[Mn];

int st[Mn]; //修建时间
int cnt1[Mm];   //第一类, 差分
int cnt2[Ms][Ms];   //第二类

int main() {
    int n,m;
    qrd(n,m);
    for(int i(1);i<=n;++i) {
        qrd(at[i].x, at[i].y);
    }
    int bd = ceil(sqrt(m)); //边界
    int sum1(0);    //前缀和
    for(int i(1);i<=m;++i) {
        int o, k;
        qrd(o,k);
        Trn& nt = at[k];
        if(nt.x+nt.y>=bd) { //第一类
            if(o==1) {
                st[k] = i;
                for(int j(i+nt.x);j<=m;j+=nt.x+nt.y) {
                    ++cnt1[j];
                }
                for(int j(i+nt.x+nt.y);j<=m;j+=nt.x+nt.y) {
                    --cnt1[j];
                }
            } else {
                for(int j(st[k]+nt.x);j<=m;j+=nt.x+nt.y) {
                    --cnt1[j];
                }
                for(int j(st[k]+nt.x+nt.y);j<=m;j+=nt.x+nt.y) {
                    ++cnt1[j];
                }
                if((i-st[k])%(nt.x+nt.y)>nt.x||(i-st[k])%(nt.x+nt.y)==0) {  // **
                    --sum1;
                }
                st[k] = 0;
            }
        } else {    //第二类
            if(o==1) {
                st[k] = i;
                for(int j(i+nt.x);j<i+nt.x+nt.y;++j) {
                    ++cnt2[nt.x+nt.y][j%(nt.x+nt.y)];
                }
            } else {
                for(int j(st[k]+nt.x);j<st[k]+nt.x+nt.y;++j) {
                    --cnt2[nt.x+nt.y][j%(nt.x+nt.y)];
                }
                st[k] = 0;
            }
        }
        sum1 += cnt1[i];
        int sum2(0);
        for(int j(1);j<bd;++j) {    //统计第二类的数量
            sum2 += cnt2[j][i%j];
        }
        printf("%d\n",sum1+sum2);
    }
    return 0;
}