一本通1549最大数

2023-11-09 17:30

文章标签 一本最大数 1549

本文主要是介绍一本通1549最大数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1549：最大数

原题来自：JSOI 2008

给定一个正整数数列

添加操作：向序列后添加一个数，序列长度变成
询问操作：询问这个序列中最后

程序运行的最开始，整数序列为空。写一个程序，读入操作的序列，并输出询问操作的答案。

第一行有两个正整数

接下来

第一个操作一定是添加操作。对于询问操作，

对于每一个询问操作，输出一行。该行只有一个数，即序列中最后

样例输入

样例输出

样例说明

最后的序列是

对于全部数据，

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int N=200005,inf=0x3f3f3f3f,Bj=200000;
 4 int m,Mod;
 5 int Root[N];
 6 struct SegmentTree
 7 {
 8     int Max[N<<2];
 9     inline void Build(int l,int r,int x)
10     {
11         Max[x]=-inf; if(l==r) return;
12         int mid=(l+r)>>1;
13         Build(l,mid,x<<1);
14         Build(mid+1,r,x<<1|1);
15         return;
16     }
17     inline void Change(int l,int r,int Pos,int Tag,int x)
18     {
19         if(l==r) {Max[x]=Tag; return;}
20         int mid=(l+r)>>1;
21         if(Pos<=mid) Change(l,mid,Pos,Tag,x<<1);
22         else Change(mid+1,r,Pos,Tag,x<<1|1);
23         Max[x]=max(Max[x<<1],Max[x<<1|1]);
24         return;
25     }
26     inline int Que(int l,int r,int ql,int qr,int x)
27     {
28         if(ql==l&&qr==r) return Max[x];
29         int mid=(l+r)>>1;
30         if(qr<=mid) return Que(l,mid,ql,qr,x<<1);
31         else if(ql>mid) return Que(mid+1,r,ql,qr,x<<1|1);
32         else return max(Que(l,mid,ql,mid,x<<1),Que(mid+1,r,mid+1,qr,x<<1|1));
33     }
34 }T;
35 int main()
36 {
37     int i,ans=0,Len=0;
38     memset(Root,0,sizeof Root);
39     T.Build(1,Bj,1);
40     scanf("%d%d",&m,&Mod);
41     for(i=1;i<=m;i++)
42     {
43         int x; char S[5];
44         scanf("%s%d",S+1,&x);
45         switch (S[1])
46         {
47             case 'A':
48                 x=(ans+x)%Mod;
49                 T.Change(1,Bj,++Len,x,1);
50                 break;
51             case 'Q':
52                 ans=T.Que(1,Bj,Len-x+1,Len,1);
53                 printf("%d\n",ans);
54                 break;
55         }
56     }
57     return 0;
58 }
59 /*
60 input
61 10 100
62 A 97
63 Q 1
64 Q 1
65 A 17
66 Q 2
67 A 63
68 Q 1
69 Q 1
70 Q 3
71 A 99
72 output
73 97
74 97
75 97
76 60
77 60
78 97
79 */

线段树

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int N=200005;
 4 int Bin[23],Log[N];
 5 int m,Mod,f[N][23];
 6 int main()
 7 {
 8     int i,j,ans=0,Len=0;
 9     Bin[0]=1; for(i=1;i<=19;i++) Bin[i]=Bin[i-1]<<1;
10     Log[0]=-1; for(i=1;i<N;i++) Log[i]=Log[i>>1]+1;
11     scanf("%d%d",&m,&Mod);
12     for(i=1;i<=m;i++)
13     {
14         int x; char S[5];
15         scanf("%s%d",S+1,&x);
16         switch (S[1])
17         {
18             case 'A':
19                 x=(x+ans)%Mod;
20                 f[++Len][0]=x;
21                 for(j=1;Bin[j]<=Len;j++) f[Len][j]=max(f[Len][j-1],f[Len-Bin[j-1]][j-1]);
22                 break;
23             case 'Q':
24                 int oo=Log[x];
25                 ans=max(f[Len][oo],f[Len-x+1+Bin[oo]-1][oo]);
26                 printf("%d\n",ans);
27                 break;
28         }
29     }
30     return 0;
31 }
32 /*
33 input
34 10 100
35 A 97
36 Q 1
37 Q 1
38 A 17
39 Q 2
40 A 63
41 Q 1
42 Q 1
43 Q 3
44 A 99
45 output
46 97
47 97
48 97
49 60
50 60
51 97
52 */