[JSOI2008]最大数线段树解法

题目描述

现在请求你维护一个数列，要求提供以下两种操作：

1、查询操作。

语法：Q L

功能：查询当前数列中末尾L个数中的最大的数，并输出这个数的值。

限制：L不超过当前数列的长度。

2、插入操作。

语法：A n

功能：将n加上t，其中t是最近一次查询操作的答案（如果还未执行过查询操作，则t=0)，并将所得结果对一个固定的常数D取模，将所得答案插入到数列的末尾。

限制：n是整数（可能为负数）并且在长整范围内。

注意：初始时数列是空的，没有一个数。

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　--by luogu

https://daniu.luogu.org/problem/show?pid=1198

先把序列的空位建好线段树，初始序列是空的，就先建为极小值（注意她是负的），对每个A操作，就是在相应位置单点修改，对每个Q操作，就是查询相应的位置的区间最值

位置是什么呢？

发现只要记下当前序列的结尾就迎刃而解啦；

代码如下：

 1 #include<cstdio>
 2 using namespace std;
 3 long long D,n,t;
 4 int tree[1000000];
 5 int m,len;
 6 void build(int ,int ,int );
 7 void change(int ,int, int ,int );
 8 int MAX(int ,int ,int ,int ,int );
 9 int main()
10 {
11     int i,j,k,l;
12     char c;
13     scanf("%d%d",&m,&D);
14     build(1,m,1);
15     for(i=1;i<=m;i++){
16         c=getchar();
17         while(c!='A'&&c!='Q')
18             c=getchar();
19         if(c=='A'){
20             scanf("%lld",&n);
21             n=(n+t)%D;
22             change(1,m,1,len+1);
23             len++;
24         }
25         if(c=='Q'){
26             scanf("%d",&l);
27             t=MAX(1,m,1,len-l+1,len);
28             printf("%lld
",t);
29         }
30     }
31     return 0;
32 }
33 void build(int l,int r,int nu){
34     if(l==r){
35         tree[nu]=-2147483600;
36         return;
37     }
38     int mid=(l+r)>>1;
39     build(l,mid,nu<<1);build(mid+1,r,nu<<1|1);
40     tree[nu]=-2147483600;
41 }
42 void change(int l,int r,int nu,int x){
43     if(l==r){
44         tree[nu]=n;
45         return ;
46     }
47     int mid=(l+r)>>1;
48     if(x<=mid)
49         change(l,mid,nu<<1,x);
50     else
51         change(mid+1,r,nu<<1|1,x);
52     if(tree[nu<<1]>tree[nu<<1|1])
53         tree[nu]=tree[nu<<1];
54     else
55         tree[nu]=tree[nu<<1|1];
56 }
57 int MAX(int l,int r,int nu,int L,int R){
58     if(L<=l&&r<=R)
59         return tree[nu];
60     int mid=(l+r)>>1;
61     int Lmax=-2147483600,Rmax=-2147483600;
62     if(L<=mid)
63         Lmax=MAX(l,mid,nu<<1,L,R);
64     if(R>=mid+1)
65         Rmax=MAX(mid+1,r,nu<<1|1,L,R);
66     if(Lmax>Rmax)
67         return Lmax;
68     return Rmax;
69 }

话说代码真难看呵；

[JSOI2008]最大数 线段树解法

题目描述

[JSOI2008]最大数线段树解法