1012: [JSOI2008]最大数maxnumber
Time Limit: 3 Sec Memory Limit: 162 MBSubmit: 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
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 }
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 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 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 } View Code 单调递减队列/ 单调递增栈 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 42 q[t++]=num; 43 } 44 else 45 { 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 } View Code 下面的代码比较挫了，如果输入序列递增，估计要超时。辅助理解单调队列思想。 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 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] 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\n",ans); 49 } 50 } 51 return 0; 52 } View Code 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 } View Code 文章链接
发表评论