1012: [JSOI2008]最大數maxnumber

Time Limit:?3 Sec??Memory Limit:?162 MB
Submit:?5425??Solved:?2397
[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

題解：先寫個線段樹拿分再說。不過我的處理方式很奇怪？不過幸好常數小。。。

1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<algorithm> 5 #include<queue> 6 #include<cstring> 7 #define PAU putchar(' ') 8 #define ENT putchar('\n') 9 #define CH for(int d=0;d<2;d++) if(ch[d]) 10 #define lson x->ch[0],L,M 11 #define rson x->ch[1],M+1,R 12 using namespace std; 13 const int maxn=200000+10,maxnode=400000+10,inf=-1u>>1; 14 int mod,last,ql,qr,pos,cv,_mx,n,len=0; 15 struct node{ 16 node*ch[2];int mx;node(){mx=-inf;} 17 void update(){mx=-inf;CH{if(ch[d]->mx>mx)mx=ch[d]->mx;}return;} 18 }seg[maxnode],*nodecnt=seg,*root; 19 void build(node*&x=root,int L=1,int R=n){ 20 x=nodecnt++;if(L==R)return;int M=L+R>>1;build(lson);build(rson);return; 21 } 22 void update(node*&x,int L,int R){ 23 if(L==R){x->mx=cv;return;}int M=L+R>>1; 24 if(pos<=M)update(lson);else update(rson);x->update(); 25 } 26 void query(node*x,int L,int R){ 27 if(ql<=L&&R<=qr){_mx=max(_mx,x->mx);return;}int M=L+R>>1; 28 if(ql<=M)query(lson);if(qr>M)query(rson);return; 29 } 30 inline int read(){ 31 int x=0,sig=1;char ch=getchar(); 32 while(!isdigit(ch)){if(ch=='-') sig=-1;ch=getchar();} 33 while(isdigit(ch)) x=10*x+ch-'0',ch=getchar(); 34 return x*sig; 35 } 36 inline void write(int x){ 37 if(x==0){putchar('0');return;}if(x<0) putchar('-'),x=-x; 38 int len=0,buf[15];while(x) buf[len++]=x%10,x/=10; 39 for(int i=len-1;i>=0;i--) putchar(buf[i]+'0');return; 40 } 41 inline char readc(){ 42 char ch=getchar();for(;!isalpha(ch);ch=getchar());return ch; 43 } 44 void init(){ 45 n=read();mod=read();build(); 46 for(int i=1;i<=n;i++){ 47 if(readc()=='A')cv=(last+read())%mod,len++,pos=len,update(root,1,n); 48 else{ 49 _mx=-inf;ql=len-read()+1;qr=len;query(root,1,n);write(_mx);ENT;last=_mx; 50 } 51 } 52 return; 53 } 54 void work(){ 55 return; 56 } 57 void print(){ 58 return; 59 } 60 int main(){ 61 init();work();print();return 0; 62 }

當然這道題還有一個神奇的做法：觀察到如果一個數出現在某個數后邊，并且這個數大于之前的數，那么之前的數無論如何也不會成為最大的數的。

所以我們可以維護一個單調的東西。然后就沒有然后了。

還有，以后別寫二分了！！！！！！！

1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<algorithm> 5 #include<queue> 6 #include<cstring> 7 #define PAU putchar(' ') 8 #define ENT putchar('\n') 9 using namespace std; 10 const int maxn=200000+10,inf=-1u>>1; 11 int s[maxn],top=0,n,mod,v[maxn],len=0,last; 12 inline int read(){ 13 int x=0,sig=1;char ch=getchar(); 14 while(!isdigit(ch)){if(ch=='-') sig=-1;ch=getchar();} 15 while(isdigit(ch)) x=10*x+ch-'0',ch=getchar(); 16 return x*=sig; 17 } 18 inline void write(int x){ 19 if(x==0){putchar('0');return;}if(x<0) putchar('-'),x=-x; 20 int len=0,buf[15];while(x) buf[len++]=x%10,x/=10; 21 for(int i=len-1;i>=0;i--) putchar(buf[i]+'0');return; 22 } 23 inline char readc(){ 24 char ch=getchar();for(;!isalpha(ch);ch=getchar());return ch; 25 } 26 void init(){ 27 n=read();mod=read(); 28 for(int i=1;i<=n;i++){ 29 if(readc()=='A'){ 30 int cv=(read()+last)%mod; 31 v[++len]=cv; 32 while(top&&v[s[top]]<=cv)top--; 33 s[++top]=len; 34 } else { 35 int pos=lower_bound(s+1,s+top+1,len-read()+1)-s; 36 write(last=v[s[pos]]);ENT; 37 } 38 } 39 return; 40 } 41 void work(){ 42 return; 43 } 44 void print(){ 45 return; 46 } 47 int main(){ 48 init();work();print();return 0; 49 }

GYH神犇還提出了離線RMQ的思想。可以發現，每一次插入數即為新建一個集合，而刪除一個數即將兩集合合并，每次詢問則為查詢一個數所在的集合的代表元素。這正好是并查集所支持的各種操作。而并查集的每次操作的均攤復雜度接近O(1)，所以RMQ的離線問題也可以在O(N+Q)的時間內解決，空間復雜度也是O(N+Q)。

但是。。。這個跟普通的二分跑得差不多，不過代碼復雜度少了很多。

1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<algorithm> 5 #include<queue> 6 #include<cstring> 7 #define PAU putchar(' ') 8 #define ENT putchar('\n') 9 using namespace std; 10 const int maxn=200000+10; 11 int stack[maxn],top=0,fa[maxn],A[maxn]; 12 int find(int x){if(fa[x]==x)return x;return fa[x]=find(fa[x]);} 13 inline int read(){ 14 int x=0,sig=1;char ch=getchar(); 15 while(!isdigit(ch)){if(ch=='-') sig=-1;ch=getchar();} 16 while(isdigit(ch)) x=10*x+ch-'0',ch=getchar(); 17 return x*=sig; 18 } 19 inline void write(int x){ 20 if(x==0){putchar('0');return;}if(x<0) putchar('-'),x=-x; 21 int len=0,buf[15];while(x) buf[len++]=x%10,x/=10; 22 for(int i=len-1;i>=0;i--) putchar(buf[i]+'0');return; 23 } 24 inline char readc(){ 25 char ch=getchar();while(!isalpha(ch))ch=getchar();return ch; 26 } 27 void init(){ 28 int last=0,m,mod,x,len=0; 29 m=read();mod=read(); 30 for(int i=1;i<=m;i++) fa[i]=i; 31 while(m--){ 32 if(readc()=='Q')x=(len-read()),write(last=A[find(x)]),ENT; 33 else{ 34 A[len]=(last+read())%mod; 35 while(top&&A[stack[~-top]]<=A[len])fa[stack[--top]]=len; 36 stack[top++]=len++; 37 } 38 } 39 return; 40 } 41 void work(){ 42 return; 43 } 44 void print(){ 45 return; 46 } 47 int main(){init();work();print();return 0;}

?

轉載于:https://www.cnblogs.com/chxer/p/4644654.html

總結

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

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