JZOJ 100149.一道联赛 A 题

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

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

那么来考虑一下复杂度。
初始时珂朵莉树中只有一段,每次修改至多增加两段,随机情况下大部分都是缩小规模。
那么复杂度大概是 i=1nlog(2i1)O(nlogn)\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);
}

arknights