這道題相對簡單下面是題目：
1012: [JSOI2008]最大數maxnumber
Time Limit: 3 Sec Memory Limit: 162 MB
Submit: 6542 Solved: 2795
[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

這個題維護一個區間最值得線段樹，根據M的最大值可以先建一個M大的空樹，然后開一個變量place記錄需要更新哪一個點，并更新即可，點修改+區間查詢 愉快的AC（話說bzoj上好久沒有一遍A了）.....

下面是代碼：

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define maxn 200001 int maxnumber[maxn<<2]={0};void updata(int now) {maxnumber[now]=max(maxnumber[now<<1],maxnumber[now<<1|1]); }void build(int l,int r,int now) {maxnumber[now]=0;if (l==r) return;int mid=(l+r)>>1;build(l,mid,now<<1);build(mid+1,r,now<<1|1);updata(now); }void point_change(int l,int r,int now,int loc,int data) {if (l==r){maxnumber[now]=data;return;}int mid=(l+r)>>1;if (loc<=mid)point_change(l,mid,now<<1,loc,data);elsepoint_change(mid+1,r,now<<1|1,loc,data);updata(now); }int query(int L,int R,int l,int r,int now) {if (L<=l && R>=r)return maxnumber[now];int mid=(l+r)>>1;int maxans=0;if (L<=mid)maxans=max(maxans,query(L,R,l,mid,now<<1));if (R>mid)maxans=max(maxans,query(L,R,mid+1,r,now<<1|1));return maxans; }int main() {int m,d;int place=1;int t=0;scanf("%d%d",&m,&d);build(1,maxn,1);for (int i=1; i<=m; i++){char command[2];scanf("%s",&command);if (command[0]=='A'){int data;scanf("%d",&data);data=(data+t) % d;point_change(1,maxn,1,place,data);place++;}else{int sum;scanf("%d",&sum);int ans=query(place-sum,place-1,1,maxn,1);printf("%d\n",ans);t=ans;}}return 0; }

轉載于:https://www.cnblogs.com/DaD3zZ-Beyonder/p/5346258.html

總結

以上是生活随笔為你收集整理的BZOJ-1012[JSOI2008]最大数maxnumber 线段树区间最值的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。