题解 P1198 【[JSOI2008]最大数】

做完之后看了那么多题解。。。 只有我用线段树没打成功然后用的单调栈？！ 可以这么想，反正查询的是后面的，就在后面加元素嘛 那么假设加入元素到top位置，但是top-1比加入的元素要小 于是我们就可以愉快地把top-1那个位置删掉了 为什么呢，，自己想 然后因为这是一个递减的单调栈查找用二分会快一些 ```cpp #include<iostream> #include<cstdio> #include<cstdlib> #define ll long long using namespace std; ll m,mod; ll zhan[2][200001];//[0]存标号[1]存数值 ll top=0; ll cnt=0;//标号 ll x,k,t; int main() { scanf("%lld%lld\n",&m,&mod); for(register int Q=1;Q<=m;Q++) { //cout<<"Q="<<Q<<endl; register char sort1[10]; scanf("%s%lld\n",sort1,&x); if(sort1[0]=='A') { k=((x+t)%mod+mod)%mod; cnt++; while(k>=zhan[1][top]&&top>0)top--; zhan[0][++top]=cnt; zhan[1][top]=k; } else { if(x==0){printf("0\n");t=0;continue;} register int l=1,r=top,res; while(l<=r) { register int mid=(l+r)>>1; if(zhan[0][mid]<cnt-x+1)l=mid+1; else r=mid-1,res=mid; } t=zhan[1][res]; printf("%lld\n",t); } //for(int i=1;i<=top;i++)printf("zhan[%d]:[0]=%d,[1]=%d\n",i,zhan[0][i],zhan[1][i]); } return 0; } ``` 好吧如果k在top位置那么比k小的在top-1，当要统计top-1到cnt的最大值的时候 一定会算到top位置，于是k比前一个数大那么前一个数就没卵用了 现在数据加强了，大家主意有L=0的情况另外字符串读入要用scanf，非常感谢@milkfilling的提醒！