1012: [JSOI2008]最大数maxnumber

Time Limit: 3 Sec  Memory Limit: 162 MB

Submit: 9851  Solved: 4318

[][][]

Description

　　现在请求你维护一个数列，要求提供以下两种操作：1、 查询操作。语法：Q L 功能：查询当前数列中末尾L

个数中的最大的数，并输出这个数的值。限制：L不超过当前数列的长度。2、 插入操作。语法：A n 功能：将n加

上t，其中t是最近一次查询操作的答案（如果还未执行过查询操作，则t=0)，并将所得结果对一个固定的常数D取

模，将所得答案插入到数列的末尾。限制：n是非负整数并且在长整范围内。注意：初始时数列是空的，没有一个

数。

Input

　　第一行两个整数，M和D，其中M表示操作的个数(M <= 200,000)，D如上文中所述，满足D在longint内。接下来

M行，查询操作或者插入操作。

Output

　　对于每一个询问操作，输出一行。该行只有一个数，即序列中最后L个数的最大数。

Sample Input

5 100

A 96

Q 1

A 97

Q 1

Q 2

Sample Output

96

93

96

HINT

 

　　数据如下http://pan.baidu.com/s/1i4JxCH3

 

Source

 

 

线段树

1 #include 
      
         2 using namespace std;  3   4 #define L(root) ((root) << 1)  5 #define R(root) (((root) << 1) | 1)  6   7 const int MAXN = 200000 + 5;  8 int numbers[MAXN];  9  10 struct Node { 11     int left, right; 12     //int sum;// 13     int mx;//最大值 14     int mid() 15     { 16         return left + ((right - left) >> 1); 17     } 18 } tree[MAXN * 4]; 19  20 void pushUp(int root) 21 { 22 //    tree[root].sum = tree[L(root)].sum + tree[R(root)].sum; 23     tree[root].mx = max(tree[L(root)].mx, tree[R(root)].mx); 24 } 25  26 void build(int root, int left, int right) 27 { 28     tree[root].left = left; 29     tree[root].right = right; 30     if (left == right) { 31 //        tree[root].sum = numbers[left]; 32         tree[root].mx = 0; 33         return; 34     } 35     int mid = tree[root].mid(); 36     build(L(root), left, mid); 37     build(R(root), mid + 1, right); 38     pushUp(root); 39 } 40  41 int query(int root, int left, int right) 42 { 43     if (tree[root].left == left && tree[root].right == right) { 44 //        return tree[root].sum; 45         return tree[root].mx; 46     } 47     int mid = tree[root].mid(); 48     if (right <= mid) { 49         return query(L(root), left, right); 50     } else if (left > mid) { 51         return query(R(root), left, right); 52     } else { 53         //return query(L(root), left, mid) + query(R(root), mid + 1, right); 54         //注意返回最大值... 55         int lv = query(L(root), left, mid); 56         int rv = query(R(root), mid + 1, right); 57         return lv > rv ? lv : rv; 58     } 59 } 60  61 void update(int root, int pos, int add) 62 { 63     if (tree[root].left == tree[root].right) { 64         //tree[root].sum = tree[root].sum + add; 65         tree[root].mx = add; 66         return; 67     } 68     int mid = tree[root].mid(); 69     if (pos <= mid) { 70         update(L(root), pos, add); 71     } else { 72         update(R(root), pos, add); 73     } 74     pushUp(root); 75 } 76  77 void test01() 78 { 79     memset(numbers, 0, sizeof(numbers)); 80     int i; 81     for (i = 1; i < MAXN; ++i) { 82         numbers[i] = i; 83     } 84     build(1, 1, 10); 85     printf("%d\n", query(1, 2, 3)); 86     update(1, 2, 100); 87     printf("%d\n", query(1, 2, 3)); 88 } 89  90 int main() 91 { 92     //test01(); 93  94     int M, D; 95     char str[2]; 96     int x; 97     int i; 98     int t; 99     int len;//当前长度100 101     while (~scanf("%d%d", &M, &D)) {102         build(1, 1, M);103 104         t = 0;105         len = 0;106         for (i = 0; i < M; ++i) {107             scanf("%1s%d", str, &x);108             if (str[0] == 'Q') {109                 t = query(1, len - x + 1, len);110                 printf("%d\n", t);111             } else {112                 update(1, ++len, (x + t) % D);113             }114         }115     }116 117     return 0;118 }
      

 

树状数组（代码好难理解，日后再看）

区间最值其实和区间求和差不多，就是将sum数组的含义转移到max，然后通过特定的区间更新max。在区间求和中，当我们维护max[i]的时候，要找到它前面所有的max[j]来更新，在这里因为是树状数组，所以可以降成一个log级，画图可知，max[i]需要的max只有max[i-2^0],max[i-2^1],max[i-2^2]..max[i-lowbit(i)+1]更新操作简单，即void change(int r) {    c[r]=num[r];    for(int i=1; i
      
       =l时，更新后，i直接-=lowbit(i)，然后继续递减。当l>=r就跳出循环int getk(int l, int r) {    int ret=num[r];    while(l<=r) {        ret=max(ret, num[r]);        for(--r; r-l>=lowbit(r); r-=lowbit(r))            ret=max(ret, c[r]);    }    return ret;}其实在这里更新操作可以和区间最值放在一起，(现在用c代表max)即c[i]=max(getk(i-lowbit(i)+1, i), num[i]);
      

1 #include 
      
        2 using namespace std; 3 #define lowbit(x) (x&-x) 4 #define max(a,b) ((a)>(b)?(a):(b)) 5 const int N=200005; 6 int num[N], c[N], cnt; 7 int getk(int l, int r) { 8     int ret=num[r]; 9     while(l<=r) {10         ret=max(ret, num[r]);11         for(--r; r-l>=lowbit(r); r-=lowbit(r))12             ret=max(ret, c[r]);13     }14     return ret;15 }16 17 int main() {18     int n, d, t=0, a;19     char ch[3];20     scanf("%d%d", &n, &d);21     while(n--) {22         scanf("%s%d", ch, &a);23         if(ch[0]=='A') {24             num[++cnt]=(t+a)%d;25             c[cnt]=max(getk(cnt-lowbit(cnt)+1, cnt-1), num[cnt]);26         }27         else {28             printf("%d\n", t=getk(cnt-a+1, cnt));29         }30     }31     return 0;32 }
      

 

单调递减队列/ 单调递增栈

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #define N 1000000 8 #define INF INT_MAX 9 10 using namespace std;11 12 //单调递减队列, [队首, 队尾], [3, 2, 1], 队列中存下标13 //单调递增栈, [栈底, 栈顶], [3, 2, 1]14 int q[N],m,d,h=1,t=1,num;15 int val[N],ans;16 17 //二分找到x后面第一个数18 inline int getans(int x)19 {20 int l=h,r=t-1,mid,res;21 while(l<=r)22 {23 mid=(l+r)>>1;24 if(x<=q[mid]) res=mid,r=mid-1;25 else l=mid+1;26 }27 return q[res];28 }29 30 inline void go()31 {32 scanf("%d%d",&m,&d);33 int a;34 char str[10];35 while(m--)36 {37 scanf("%s%d",str,&a);38 if(str[0]=='A')39 {40 val[++num]=(a+ans)%d;41 while(h
            
             <=val[num]) t--;42 q[t++]=num;43 }44 else45 {46 //二分47 ans=val[getans(num-a+1)];48 printf("%d\n",ans);49 }50 }51 }52 53 int main()54 {55 go();56 return 0;57 }
            
           
          
         
        
       
      

下面的代码比较挫了，如果输入序列递增，估计要超时。辅助理解单调队列思想。

1 //qscqesze 2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
          
            7 #include 
           
             8 #include 
            
              9 #include 
             
              10 #include 
              
               11 #include 
               
                12 #include 
                
                 13 #include 
                 
                  14 #include 
                  
                 
                
               
              
             
            
           
          
         
        
       
      

 

rmq（我写的这个速度有点捉急...）

1 #include 
      
        2 using namespace std; 3  4 const int MAXN = 200000 + 5; 5 int mx[MAXN][20]; 6 int num[MAXN]; 7 int tot; 8  9 void update()10 {11     mx[tot][0] = num[tot];12     int k1 = log2(tot);13     int k2;14     int i, j;15     for (j = 1; j <= k1; ++j) {16         k2 = tot - pow(2, j) + 1;17         for (i = k2; i <= k2; ++i) {18             mx[i][j] = max(mx[i][j - 1], mx[i + (int)pow(2, j - 1)][j - 1]);19         }20     }21 }22 23 int rmq(int i, int j)24 {25     int k = log2(j - i + 1);26     return max(mx[i][k], mx[j - (int)pow(2, k) + 1][k]);27 }28 29 int main()30 {31     int M, D;32     char str[2];33     int x;34     int i;35     int t;36 37     while (~scanf("%d%d", &M, &D)) {38         tot = 0;39         t = 0;40         for (i = 0; i < M; ++i) {41             scanf("%1s%d", str, &x);42             if (str[0] == 'Q') {43                 t = rmq(tot - x + 1, tot);44                 printf("%d\n", t);45             } else {46                 num[++tot] = (x + t) % D;47                 update();48             }49         }50     }51 52     return 0;53 }