As another one of their crazy antics, the N (1 ≤ N ≤ 100,000) cows want Farmer John to race against the clock to answer some of their pressing questions.

The cows are lined up in a row from 1 to N, and each one is holding a sign representing a number, Ai (1 ≤ Ai≤ 1,000,000,000). The cows need FJ to perform Q (1 ≤ Q ≤ 50,000) operations, which can be either of the following:

  • Modify cow i's number to X (1 ≤ X ≤ 1,000,000,000). This will be represented in the input as a line containing the letter M followed by the space-separated numbers i and X.
  • Count how many cows in the range [P, Q] (1 ≤ P ≤ Q ≤ N) have Ai ≤ X (0 ≤ X ≤ 1,000,000,000). This will be represented in the input as a line containing the letter C followed by the space-separated numbers P, Q, and X.

Of course, FJ would like your help.

Input

The first line gives the integers N and Q, and the next N lines give the initial values of Ai. Finally, the next Q lines each contain a query of the form "M i X" or "C P Q X".

Output

Print the answer to each 'C' query, one per line.

Example

Input: 4 6 3 4 1 7 C 2 4 4 M 4 1 C 2 4 4 C 1 4 5 M 2 10 C 1 3 9  Output: 2 3 4 2

题意：给出一段序列，要求有两种操作， 1 修改一个位置的数字， 2 查询一段区间内的小于val的数字有多少个。

sl: 这是区间查询，所以用线段树维护就好了，但是查询小于val的数字有多少个，所以直接随便用一个平衡树求一个rank就好了。 最近刚刚学了SBT.

试了试模板，还是要手敲为妙。 加了挂还是超时，不知道为何。 应该有好方法。 用treap貌似能过？

  1 #include <iostream>

  2 #include <cstring>

  3 #include <cstdio>

  4 #include <algorithm>

  5 #include <cmath>

  6 

  7 using namespace std;

  8 

  9 const int maxn = ;

 10 

 11 struct Node {

 12     int key, val;

 13     Node(){};

 14     Node(int a, int b) { key = a; val = b; }

 15     bool operator < (Node b)  { return val < b.val; }

 16     bool operator <= (Node b) { return val <= b.val; }

 17     bool operator > (Node b)  { return val > b.val; }

 18     bool operator >= (Node b) { return val >= b.val; }

 19     bool operator == (Node b) { return val == b.val; }

 20     Node operator + (int a) {

 21         return Node(key, val+a) > Node(key, val) ? Node(key, val+a) : Node(key, val-a);

 22     }

 23 };

 24 

 25 int sz[maxn*];

 26 int key[maxn*];

 27 int lch[maxn*];

 28 int rch[maxn*];

 29 int tot;

 30 

 31 template<typename Type>

 32 class SBT

 33 {

 34 public:

 35     SBT() { Clear(); }

 36     void Clear() { root = ; lch[] = rch[] = sz[] = ; }

 37     static void ClearAll() { tot = ; }

 38     int Size() { return sz[root]; }

 39     bool Empty() { return  == sz[root]; }

 40     bool Find(Type k) { return Find(root, k); }

 41     void InsertR(Type k) { Insert(root, k); } // 可重复插入

 42     void Insert(Type k) { if (!Find(k)) Insert(root, k); }

 43     void Delete(Type k) { if (Find(k)) Delete(root, k); }

 44     void DeleteSmaller(Type k) { DeleteSmaller(root, k); }

 45     int GetRank(Type k) { return GetRank(root, k); }

 46     Type GetKth(int k) { return GetKth(root, k); }

 47     Type GetMin() { return GetKth(root, ); }

 48     Type GetMax() { return GetKth(root, Size()); }

 49     Type GetPre(Type k) { return GetPre(root, k); }

 50     Type GetSuc(Type k) { return GetSuc(root, k); }

 51     int GetSmaller(Type k) { return GetSmaller(root, k); } // 返回小于k的元素的个数

 52 

 53 private:

 54     void LeftRotate(int &t) {

 55         int k = rch[t];

 56         rch[t] = lch[k];

 57         lch[k] = t;

 58         sz[k] = sz[t];

 59         sz[t] =  + sz[lch[t]] + sz[rch[t]];

 60         t = k;

 61     }

 62     void RightRotate(int &t) {

 63         int k = lch[t];

 64         lch[t] = rch[k];

 65         rch[k] = t;

 66         sz[k] = sz[t];

 67         sz[t] =  + sz[lch[t]] + sz[rch[t]];

 68         t = k;

 69     }

 70     void Maintain(int &t, bool flag) {

 71         if ( == t) return ;

 72         if (false == flag) {

 73             if (sz[lch[lch[t]]] > sz[rch[t]]) {

 74                 RightRotate(t);

 75             } else if (sz[rch[lch[t]]] > sz[rch[t]]) {

 76                 LeftRotate(lch[t]);

 77                 RightRotate(t);

 78             } else {

 79                 return ;

 80             }

 81         } else {

 82             if (sz[rch[rch[t]]] > sz[lch[t]]) {

 83                 LeftRotate(t);

 84             } else if (sz[lch[rch[t]]] > sz[lch[t]]) {

 85                 RightRotate(rch[t]);

 86                 LeftRotate(t);

 87             } else {

 88                 return ;

 89             }

 90         }

 91         Maintain(lch[t], false);

 92         Maintain(rch[t], true);

 93         Maintain(t, false);

 94         Maintain(t, true);

 95     }

 96     Type GetPre(int t, Type k) {

 97         if ( == k) return k;

 98         if (k <= key[t]) return GetPre(lch[t], k);

 99         Type tmp = GetPre(rch[t], k);

         if (tmp == k) return key[t];

         return tmp;

     }

     Type GetSuc(int t, Type k) {

         if ( == root) return k;

         if (k >= key[t]) return GetSuc(rch[t], k);

         Type tmp = GetSuc(lch[t], k);

         if (tmp == k) return key[t];

         return tmp;

     }

     Type GetKth(int t, int k) {

         if (sz[lch[t]] >= k) return GetKth(lch[t], k);

         if (sz[lch[t]] == k - ) return key[t];

         return GetKth(rch[t], k - sz[lch[t]] - );

     }

     int GetRank(int t, Type k) {

         if ( == t) return ;

         if (k < key[t]) return GetRank(lch[t], k);

         return sz[lch[t]] +  + GetRank(rch[t], k);

     }

     int GetSmaller(int t, Type k) {

         if ( == t) return ;

         if (k <= key[t]) return GetSmaller(lch[t], k);

         return sz[lch[t]] +  + GetSmaller(rch[t], k);

     }

     bool Find(int t, Type k) {

         if ( == t) return false;

         else if (k < key[t]) return Find(lch[t], k);

         else return (key[t] == k || Find(rch[t], k));

     }

     void Insert(int &t, Type k) {

         if ( == t) {

             t = ++tot;

             lch[t] = rch[t] = ;

             sz[t]= ;

             key[t] = k;

             return ;

         }

         sz[t]++;

         if (k < key[t]) Insert(lch[t], k);

         else Insert(rch[t], k);

         Maintain(t, k >= key[t]);

     }

     void DeleteSmaller(int &t , Type k) {

         if ( == t) return ;

         if ( key[t] < k ) {

             t = rch[t];

             DeleteSmaller(t , key);

         } else {

             DeleteSmaller(lch[t] , k);

             sz[t] =  + sz[lch[t]] + sz[rch[t]];

         }

     }

     Type Delete(int &t, Type k) {

         sz[t]--;

         if ((key[t] == k) || (k < key[t] &&  == lch[t]) || (k > key[t] &&  == rch[t])) {

             Type tmp = key[t];

             if ( == lch[t] ||  == rch[t]) {

                 t = lch[t] + rch[t];

             } else {

                 key[t] = Delete(lch[t], key[t] + );

             }

             return tmp;

         } else {

             if (k < key[t]) {

                 return Delete(lch[t], k);

             } else {

                 return Delete(rch[t], k);

             }

         }

     }

 private:

     int root;

 };

 

 SBT <int> sbt[maxn<<];

 int a[maxn];

 

 void build(int L,int R,int o) {

     sbt[o].Clear();

     for(int i=L;i<=R;i++) {

         sbt[o].InsertR(a[i]);

     }

     if(L==R) return ;

     int mid=(L+R)>>;

     build(L,mid,o<<);

     build(mid+,R,o<<|);

 }

 void Update(int L,int R,int o,int pos,int val) {

     sbt[o].Delete(a[pos]);

     sbt[o].InsertR(val);

     if(L==R) return ;

     int mid=(L+R)>>;

     if(pos<=mid) Update(L,mid,o<<,pos,val);

     if(pos>mid) Update(mid+,R,o<<|,pos,val);

 }

 

 int Query(int L,int R,int o,int ls,int rs,int val) {

     if(ls<=L&&rs>=R) {

         return sbt[o].GetRank(val);

     }

     int mid=(L+R)>>; int res=;

     if(ls<=mid) res+=Query(L,mid,o<<,ls,rs,val);

     if(rs>mid) res+=Query(mid+,R,o<<|,ls,rs,val);

     return res;

 }

 inline int read()

 {

     int m=;

     char ch=getchar();

     while(ch<''||ch>''){ch=getchar(); }

     while(ch>=''&&ch<=''){m=m*+ch-''; ch=getchar(); }

     return m;

 }

 int main() {

     int n,m; char op[];

     int ls,rs,val;

     while(scanf("%d %d",&n,&m)==) {

         for(int i=;i<=n;i++) {

             a[i]=read();

         }

         SBT<int> :: ClearAll();

         build(,n,);

         for(int i=;i<=m;i++) {

             scanf("%s",op);

             if(op[]=='C') {

                 ls=read(); rs=read(); val=read();

                 int ans=Query(,n,,ls,rs,val);

                 printf("%d\n",ans);

             }

             else {

                 ls=read(); rs=read();

                 Update(,n,,ls,val);

                 a[ls]=val;

             }

         }

     }

     return ;

238 }

最新文章

  1. 数据结构0103汉诺塔&amp;八皇后
  2. eclipse debug maven项目时出现缺少库的问题
  3. Windows 安装 openssl
  4. AJAX原理总结
  5. [C++] socket - 2 [UDP通信C/S实例]
  6. windows 2008 怎么对外开放端口
  7. JS实现rgb与16进制颜色相互转换
  8. （一）JAVA使用POI操作excel
  9. cocos2d(x) HTML label ;CCHTML CCHTMLLabel
  10. 详解Windows Server 2008 R2下安装Oracle 11g
  11. c++模板使用及实现模板声明定义的分离
  12. pandas 对数据帧DataFrame中数据的索引及切片操作
  13. Python之旅Day15 Bootstrap与Django初识
  14. Mybatis 缓存分析
  15. js判断数组是否包含某个字符串变量的实例
  16. C# Dictionary, SortedDictionary, SortedList
  17. 2017-2018-2 20155203《网络对抗技术》Exp5 MSF基础应用
  18. RecyclerView的滚动事件OnScrollListener研究
  19. stm32调试过程中如何判断是程序问题还是硬件问题？
  20. FTP 主动模式 与被动模式

热门文章

  1. 题解报告：poj 3061 Subsequence（前缀+二分or尺取法）
  2. [转]C#委托Action、Action&lt;T&gt;、Func&lt;T&gt;、Predicate&lt;T&gt;
  3. Scala基础篇-04 try表达式
  4. iOS----时间日期处理
  5. InChatter系统之客户端消息处理中心
  6. LigerUI用Post\Get\Ajax前后台交互方式的写法
  7. Asp.Net 设计模式 之 “简单工厂”模式
  8. Shell书籍推荐
  9. Win10上 visual studio设置为本地IIS运行网站时 必须以管理员身份加载项目的解决方法
  10. No-2.注释