珂朵莉树入门就被洛谷卡掉了，后续再补 洛谷P2787 语文1（chin1）- 理理思维

  1 /*
  2 set 自带的 lower_bound 和 upper_bound 的时间复杂度为 O(logn)。
  3 
  4 但使用 algorithm 库中的 lower_bound 和 upper_bound 函数对 set 中的元素进行查询，时间复杂度为 0(n)。
  5 
  6 总结：对于可随机访问的有序容器使用 algorithm 库中的 lower_bound 和 upper_bound 函数时间复杂度为O(logn)，
  7 
  8 但对于set，multiset这种不能随机访问的有序容器，要用其自带的 lower_bound 和 upper_bound 的时间复杂度才为 O(logn)。
  9 
 10 */
 11 #include
 12 using namespace std;
 13 struct node
 14 {
 15     mutable int l, r, val;
 16     node(int L =  0, int R= 0 , int V=0 ) : l(L), r(R), val(V){}
 17     bool operator < (const node &a)const
 18     {
 19         return l < a.l;
 20     }
 21      
 22 };
 23 setmys;
 24 inline int change(int a){return a <= 90 ? a : (a^32);}
 25 
 26 auto split(int pos)
 27 {
 28     auto it = mys.lower_bound((node)pos);
 29     if(it != mys.end() && it->l == pos)return it;
 30     it--;
 31     int l = it->l, r = it->r, val = it->val;
 32     mys.erase(it);
 33     mys.insert((node){l, pos-1, val});
 34     return mys.insert((node){pos , r, val}).first;
 35 }
 36 
 37 int getcnt(int l, int r, int val)
 38 {
 39     int sum=0;
 40     auto it2 = split(r+1), it1 = split(l);
 41     for(;it1!=it2;it1++)
 42     if(it1->val == val)sum += it1->r - it1->l + 1;
 43     return sum;    
 44 }
 45 void modify(int l, int r, int val)
 46 {
 47     auto it2 = split(r+1), it1 = split(l);
 48     mys.erase(it1,it2);
 49     mys.insert((node){l, r, val});
 50 }
 51 void rev(int l, int r)
 52 {
 53     auto it2 = split(r+1), it1 = split(l);
 54     auto it=it1;
 55     int ch[91];
 56     memset(ch,0,sizeof(ch));
 57     for(; it != it2; it++)ch[it->val] += it->r - it->l + 1;
 58     mys.erase(it1,it2);
 59     for(int i = 65; i <= 90; i++)
 60     if(ch[i])
 61     {    
 62         mys.insert((node){l, ch[i] + l - 1, i});
 63         l += ch[i];
 64     }
 65 }
 66 int main()
 67 {
 68     //freopen("P2787_11.in","r",stdin);
 69     //freopen("out","w",stdout);
 70     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
 71     int n, m, l, r,opt;
 72     char ch,val;
 73     cin>>n>>m;
 74     for(int i = 1; i <= n; i++)
 75     {
 76         cin>>ch;
 77         mys.insert((node){i, i, change(ch)});
 78     }
 79     for(int i = 1; i <= m; i++)
 80     {
 81         cin>>opt;
 82         if(opt == 1)
 83         {
 84             cin>>l>>r>>val;
 85             int ans = getcnt(l, r, change(val));
 86             cout<'\n'; 
 87         }
 88         else if(opt == 2)
 89         {
 90             cin>>l>>r>>val;
 91             modify(l, r, change(val));
 92         }
 93         else if(opt == 3)
 94         {
 95             cin>>l>>r;
 96             rev(l, r);
 97         }
 98     }
 99     return 0;
100 }