Description

現(xiàn)在請(qǐng)求你維護(hù)一個(gè)數(shù)列，要求提供以下兩種操作： 1、 查詢操作。語(yǔ)法：Q L 功能：查詢當(dāng)前數(shù)列中末尾L個(gè)數(shù)中的最大的數(shù)，并輸出這個(gè)數(shù)的值。限制：L不超過(guò)當(dāng)前數(shù)列的長(zhǎng)度。 2、 插入操作。語(yǔ)法：A n 功能：將n加上t，其中t是最近一次查詢操作的答案（如果還未執(zhí)行過(guò)查詢操作，則t=0)，并將所得結(jié)果對(duì)一個(gè)固定的常數(shù)D取模，將所得答案插入到數(shù)列的末尾。限制：n是非負(fù)整數(shù)并且在長(zhǎng)整范圍內(nèi)。注意：初始時(shí)數(shù)列是空的，沒有一個(gè)數(shù)。

Input

第一行兩個(gè)整數(shù)，M和D，其中M表示操作的個(gè)數(shù)(M <= 200,000)，D如上文中所述，滿足(0

Output

對(duì)于每一個(gè)查詢操作，你應(yīng)該按照順序依次輸出結(jié)果，每個(gè)結(jié)果占一行。

Sample Input

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

Sample Output

96
93
96

HINT

Source

額，不知道怎么形容這道題。樹狀數(shù)組5min再見吧！！！

1 #include<cstring> 2 #include<cstdio> 3 #include<iostream> 4 #include<cstdlib> 5 using namespace std; 6 7 #define maxn 200010 8 #define inf (1<<30) 9 int tree[maxn],d,ans,n,m; 10 11 inline int lowbit(int a) {return a & (-a);} 12 13 inline void modify(int a,int b) 14 { 15 while (a <= m) 16 { 17 tree[a] = max(tree[a],b); 18 a += lowbit(a); 19 } 20 } 21 22 inline int find(int a) 23 { 24 int ret = -inf; 25 for (;a;a -= lowbit(a)) ret = max(ret,tree[a]); 26 return ret; 27 } 28 29 int main() 30 { 31 freopen("1012.in","r",stdin); 32 freopen("1012.out","w",stdout); 33 scanf("%d %d\n",&m,&d); int i; 34 memset(tree,128,sizeof(tree)); 35 for (i = 1;i <= m;++i) 36 { 37 char opt; int a;scanf("%c %d\n",&opt,&a); 38 if (opt == 'Q') 39 { 40 ans = find(m-n+a); 41 printf("%d\n",ans); 42 } 43 else 44 { 45 a = a % d + ans % d; 46 a %= d; 47 ++n; 48 modify(m-n+1,a); 49 } 50 } 51 fclose(stdin); fclose(stdout); 52 return 0; 53 } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/mmlz/p/4226141.html

總結(jié)

以上是生活随笔為你收集整理的BZOJ 1012 最大数的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。