大视野 1012: [JSOI2008]最大数maxnumber（线段树/ 树状数组/ 单调队列/ 单调栈/ rmq）

1012: [JSOI2008]最大数maxnumber

Time Limit: 3 Sec Memory Limit: 162 MB
Submit: 9851 Solved: 4318
[Submit][Status][Discuss]

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 <bits/stdc++.h>
  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
", query(1, 2, 3));
 86     update(1, 2, 100);
 87     printf("%d
", 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
", t);
111             } else {
112                 update(1, ++len, (x + t) % D);
113             }
114         }
115     }
116 
117     return 0;
118 }

View Code

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

区间最值其实和区间求和差不多，就是将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<lowbit(r); i<<=1)
        c[r]=max(c[r], c[r-i]);
}
接下来是求区间最值，很容易看出，我们找[l,r]的最值就是找在次区间的max，即递减r，在这里可以有个优化，即当找到一个max[i]，有i-lowbit(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]);

View Code

 1 #include <cstdio>
 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
", t=getk(cnt-a+1, cnt));
29         }
30     }
31     return 0;
32 }

View Code

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

 1 #include <iostream>
 2 #include <cstdlib>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <algorithm>
 6 #include <climits>
 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<t&&val[q[t-1]]<=val[num]) t--;
42             q[t++]=num;
43         }
44         else
45         {
46             //二分
47             ans=val[getans(num-a+1)];
48             printf("%d
",ans);
49         }
50     }
51 }
52 
53 int main()
54 {
55     go();
56     return 0;
57 }

View Code

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

 1 //qscqesze
 2 #include <cstdio>
 3 #include <cmath>
 4 #include <cstring>
 5 #include <ctime>
 6 #include <iostream>
 7 #include <algorithm>
 8 #include <set>
 9 #include <vector>
10 #include <sstream>
11 #include <queue>
12 #include <typeinfo>
13 #include <fstream>
14 #include <map>
15 typedef long long ll;
16 using namespace std;
17 //freopen("D.in","r",stdin);
18 //freopen("D.out","w",stdout);
19 #define sspeed ios_base::sync_with_stdio(0);cin.tie(0)
20 #define maxn 250001
21 #define eps 1e-9
22 const int inf=0x7fffffff;   //无限大 
23 //**************************************************************************************
24 int a[maxn],max_num[maxn],t=0,ans=0;
25 int main()
26 {
27     int n,d;
28     scanf("%d%d",&n,&d);
29     char ch[3];
30     int g;
31     while(n--)
32     {
33         scanf("%s%d",ch,&g);
34         if(ch[0]=='A')
35         {
36             a[++t]=(ans+g)%d;
37             for(int i=t;i;i--)
38             {
39                 if(max_num[i]<a[t])
40                     max_num[i]=a[t];
41                 else
42                     break;
43             }
44         }
45         else
46         {
47             ans=max_num[t-g+1];
48             printf("%d
",ans);
49         }
50     }
51     return 0;
52 }

View Code

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

 1 #include <bits/stdc++.h>
 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
", t);
45             } else {
46                 num[++tot] = (x + t) % D;
47                 update();
48             }
49         }
50     }
51 
52     return 0;
53 }

View Code