JSOI2008最大数--数据结构

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

这道题有三个做法呢

第一个就是普通的线段树
太懒了不打了

第二个可以单调栈+二分
维护一个单调递减的单调栈
每次加入数的时候
把这个数前面小于它的都删掉
然后查询的时候二分找到最前面的在所求范围内的
但是话说这种方法好像被加强的数据卡了？？？
我也不带了优化了
泥萌自己优化一下看能不能过···
不过这种比较新颖的想法应该都是对着卡才能卡过吧
而且代码很短思路清晰
也不容易写错
总之是一个很不错的选择啦！

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#define maxn 200005
using namespace std;
int tot,num;
long long d,t,m;inline long long rd(){long long x=0,fla=1; char c=' ';while(c>'9' || c<'0') {if(c=='-') fla=-fla;c=getchar();}while(c<='9' && c>='0') x=x*10+c-'0', c=getchar();return x*fla;
}struct stacck{int pos;long long w;
}stk[maxn];inline void check(int num,long long x){while(tot>0 && x>=stk[tot].w) tot--;stk[++tot].w=x;stk[tot].pos=num;
}inline long long query(int L,int l,int r){while(l<r){int mid=(l+r)>>1;if(stk[mid].pos>=L) r=mid;else l=mid+1;}return stk[r].w;
}int main()
{m=rd(); d=rd();while(m--){char ch=getchar();while(ch!='A' && ch!='Q') ch=getchar();long long x=rd();if(ch=='A'){num++;x=(x+t)%d;check(num,x);}else{if(x==0) {printf("0\n");continue;}t=query(num-x+1,1,tot);printf("%lld\n",t);}}return 0;
}

第三种
这道题用分块也能做耶
而且比线段树快好多
这种比较暴力的也比较好打的耶【虽然下面这个不是我打的】

代码：

#include<cstdio>
#include<iostream>
#include<cmath> 
#define neko 200010
#define chkmin(a,b) ((a)<(b)?(a):(b))
#define chkmax(a,b) ((a)>(b)?(a):(b))
#define f(i,a,b) for(register int i=(a);i<=(b);i=-(~(i)))
using std::cin;
typedef long long ll;
int p,blk,m,bl[neko];
ll mod,t,a[neko],Max[neko];
template<typename T>
void read(T &x)
{char c=getchar();x=0;while(!isdigit(c))c=getchar();while(isdigit(c)){x=(x<<1)+(x<<3)+(c^'0');c=getchar();}
}
void update(ll x)
{if(x>=mod)x%=mod;if(x<0)x+=mod;bl[++p]=(p-1)/blk+1,a[p]=x;Max[bl[p]]=chkmax(Max[bl[p]],x);
}
ll query(int l,int r)
{ll tmp=-3e9;f(i,l,chkmin(bl[l]*blk,r))tmp=chkmax(tmp,a[i]);f(i,bl[l]+1,bl[r]-1)tmp=chkmax(tmp,Max[i]);f(i,chkmax((bl[r]-1)*blk+1,l),r)tmp=chkmax(tmp,a[i]);return t=tmp;
}
int main()
{std::ios::sync_with_stdio(false);char c;int x;ll y;cin>>m>>mod;blk=sqrt(m)/2;f(i,1,m){        cin>>c; if(c=='A')cin>>x,update(x+t);if(c=='Q'){cin>>y;if(y==0) printf("0\n");else printf("%lld\n",query(p-y+1,p));}}return 0;
}