CF1638E

发表于 更新于 分类于
Colorful Operations

Colorful Operations

神奇均摊科技。

哈哈哈我连 CF 数据结构题都不能场切哈哈哈。

颜色加可以直接做一个颜色标记累加在上面。

修改区间的时候直接暴力找到每个该区间内线段树上颜色相同的子区间并打上懒标记，最后查询的时候直接在线段树上单点查即可（比较 Trivial 的 lazytag 下传）。

然后就没了。

为什么这个复杂度是对的？

我们知道，每次染色操作，至多会增加 $O(1)$ 个颜色相同的子区间。我们假设第 $i$ 次操作的区间中有 $O(\Delta x_i)$ 个颜色相同的子区间（不是线段树上的）需要暴力修改，则必然在之前需要 $O(\Delta x_i)$ 次染色操作，从而有 $O(\sum \Delta x_i)\le O(q)$，因此需要操作的颜色相同的子区间数量为 $O(q)$ 个。

但是我们是在线段树上操作的，意味着每个这样颜色相同的子区间我们都需要把它拆分成 $\log$ 个线段树上的区间，从而我们的染色操作的总复杂度是 $O(q\log n)$ 的。

这样，我们最终的复杂度就是 $O((n+q)\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
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
#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;

const ll N=1e6;

ll n,q;
ll tag_val[N+5];
char s[10];

struct Sgt{
  ll tag_same,tag_laz;
  #define tag_same(x) tree[x].tag_same
  #define tag_laz(x) tree[x].tag_laz
}tree[N*4+5];

inline void Build(ll p,ll l,ll r) {
  tag_same(p)=1;
  if(l==r) return;ll mid=(l+r)>>1;
  if(l<=mid) Build(p<<1,l,mid);
  if(r>mid) Build(p<<1|1,mid+1,r);
}

inline void Pushup(ll p) {
  if(tag_same(p<<1)==tag_same(p<<1|1)) tag_same(p)=tag_same(p<<1);
  else tag_same(p)=0;
}

inline void Pushdown(ll p) {
  tag_laz(p<<1)+=tag_laz(p);tag_laz(p<<1|1)+=tag_laz(p);
  if(tag_same(p)) {
    tag_same(p<<1)=tag_same(p<<1|1)=tag_same(p);
  }
  tag_laz(p)=0;
}

inline void Modify(ll p,ll lp,ll rp,ll l,ll r,ll col) {
  if(lp>=l&&rp<=r) {
    if(tag_same(p)) {
      tag_laz(p)+=tag_val[tag_same(p)];
      tag_laz(p)-=tag_val[col];
      tag_same(p)=col;
      return;
    }
    ll mid=(lp+rp)>>1;
    Modify(p<<1,lp,mid,l,r,col);Modify(p<<1|1,mid+1,rp,l,r,col);
    Pushup(p);
    return;
  }
  ll mid=(lp+rp)>>1;Pushdown(p);
  if(l<=mid) Modify(p<<1,lp,mid,l,r,col);
  if(r>mid) Modify(p<<1|1,mid+1,rp,l,r,col);
  Pushup(p);
}

inline ll Ask(ll p,ll lp,ll rp,ll x) {
  if(lp==rp) return tag_laz(p)+tag_val[tag_same(p)];
  ll mid=(lp+rp)>>1;Pushdown(p);
  if(x<=mid) return Ask(p<<1,lp,mid,x);
  else return Ask(p<<1|1,mid+1,rp,x);
}

inline ll read() {
  ll ret=0,f=1;char ch=getchar();
  while(ch<48||ch>57) {if(ch==45) f=-f;ch=getchar();}
  while(ch>=48&&ch<=57) {ret=(ret<<3)+(ret<<1)+ch-48;ch=getchar();}
  return ret*f;
}

inline void write(ll x) {
  static char buf[22];static ll len=-1;
  if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
  else {putchar(45);do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
  while(len>=0) putchar(buf[len--]);
}

inline void writeln(ll x) {write(x);putchar(10);}

int main() {

  n=read();q=read();
  Build(1,1,n);

  while(q--) {
    scanf("%s",s);
    if(s[0]=='C') {
      ll l,r,c;
      l=read();r=read();c=read();
      Modify(1,1,n,l,r,c);
    }
    if(s[0]=='A') {
      ll c,x;
      c=read();x=read();tag_val[c]+=x;
    }
    if(s[0]=='Q') {
      ll x=read();
      writeln(Ask(1,1,n,x));
    }
  }

  return 0;
}