JZOJ 100149 一道联赛 A 题

发表于 | 分类于 |

这题一眼上珂朵莉树（
复杂度大概是对的？

在修改的同时维护 \(cnt_x\) 表示当前序列中颜色为 \(x\) 的元素个数。
只需在修改时依次去除原来区间的贡献并加上修改后的贡献即可。

那么来考虑一下复杂度。
初始时珂朵莉树中只有一段，每次修改至多增加两段，随机情况下大部分都是缩小规模。
那么复杂度大概是 \(\sum\limits_{i = 1}^n \log (2i - 1) \approx O(n \log 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
#include <cstdio>
#include <algorithm>
#include <set>
using namespace std;
const int N = 1e5;
const int A = 1e5;
int n,c,m;
int cnt[A + 5];
struct node
{
    int l,r,v;
    inline bool operator<(const node &o) const
    {
        return l < o.l;
    }
};
set<node> d;
typedef set<node>::iterator IT;
IT split(int x)
{
    if(x >= n)
        return d.end();
    IT it = --d.upper_bound((node){x,0,0});
    if(it->l == x)
        return it;
    int l = it->l,r = it->r,v = it->v;
    d.erase(it);
    d.insert((node){l,x - 1,v});
    return d.insert((node){x,r,v}).first;
}
void assign(int l,int r,int v)
{
    IT itr = split(r + 1),itl = split(l);
    for(register IT it = itl;it != itr;++it)
        cnt[it->v] -= it->r - it->l + 1;
    d.erase(itl,itr);
    cnt[v] += r - l + 1;
    d.insert((node){l,r,v});
}
int main()
{
    scanf("%d%d%d",&n,&c,&m);
    d.insert((node){0,n - 1,1});
    cnt[1] += n;
    int p,x;
    long long a,b;
    while(m--)
    {
        scanf("%d%d%lld%lld",&p,&x,&a,&b);
        long long s = cnt[p];
        int l = (a + s * s) % n;
        int r = (a + (s + b) * (s + b)) % n;
        if(l > r)
            swap(l,r);
        assign(l,r,x);
    }
    int ans = 0;
    for(register int i = 1;i <= c;++i)
        if(cnt[i] > ans)
            ans = cnt[i];
    printf("%d\n",ans);
}