bzoj1012线段树

线段树维护序列。。

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstdlib>
 4 #include<cstring>
 5 #include<ctime>
 6 #include<cmath>
 7 #include<algorithm>
 8 #define mid(l,r) ((l+r)>>1)
 9 #define l(a) (a<<1)
10 #define r(a) ((a<<1)+1)
11 #define rep(i,l,r) for(int i=l;i<r;i++)
12 #define clr(a,x) memset(a,x,sizeof(a))
13 using namespace std;
14 const int maxm=200050,inf=0x3fffffff;
15 int read()
16 {
17     int ans=0,f=1;
18     char c=getchar();
19     while(!isdigit(c)){
20         if(c=='-') f=-1;
21         c=getchar();
22     }
23     while(isdigit(c)){
24         ans=ans*10+c-'0';
25         c=getchar();
26     }
27     return ans*f;
28 }
29 struct node{
30     int l,r,mx;
31 };
32 node x[maxm<<2];
33 int f[maxm];
34 void update(int a)
35 {
36     x[a].mx=max(x[l(a)].mx,x[r(a)].mx);
37 }
38 void build(int a,int l,int r)
39 {    
40     x[a].l=l;x[a].r=r;x[a].mx=0;
41     if(l==r){
42         f[l]=a;
43         return;
44     }
45     build(l(a),l,mid(l,r));
46     build(r(a),mid(l,r)+1,r);
47     update(a);
48 }
49 void maintain(int a)
50 {    
51     int f=x[a].mx;
52     update(a);
53     if(a!=1&&f!=x[a].mx) maintain(a>>1);
54 }
55 void add(int k,int d)
56 {
57     x[f[k]].mx+=d;
58     maintain(f[k]>>1);
59 }
60 int find(int a,int l,int r)
61 {    
62     if(l==x[a].l&&r==x[a].r) return x[a].mx;
63     if(r<=mid(x[a].l,x[a].r)) return find(l(a),l,r);
64     if(l>mid(x[a].l,x[a].r)) return find(r(a),l,r);
65     return max(find(l(a),l,mid(x[a].l,x[a].r)),find(r(a),mid(x[a].l,x[a].r)+1,r));
66 }
67 int main()
68 {    
69     int m=read(),p=read(),pre=0,cnt=0;
70     build(1,1,m);
71     while(m--){
72         char opt=getchar();
73         while(opt!='A'&&opt!='Q') opt=getchar();
74         int t=read();
75         if(opt=='A'){
76             cnt++;
77             add(cnt,(t+pre)%p);
78         }else{
79             pre=find(1,cnt-t+1,cnt);
80             printf("%d
",pre);
81         }    
82     }
83     return 0;
84 }

View Code

1012: [JSOI2008]最大数maxnumber

Time Limit: 3 Sec Memory Limit: 162 MB
Submit: 5373 Solved: 2378
[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如上文中所述，满足(0

Output

对于每一个查询操作，你应该按照顺序依次输出结果，每个结果占一行。

Sample Input

5 100
A 96
Q 1
A 97
Q 1
Q 2

Sample Output

96
93
96

HINT

Source

[Submit][Status][Discuss]