准备写线段树写法
所以先搁置一下23333
（啊我debug半个点失败
可能我今天不适合写题解【微笑
拖图片拖了五分钟，总是一点就变成预览模式
气得我想砸电脑
mmp
线段树写法也没写出来
心情好差www
【啊好的发泄完毕好轻松
emmmm
那么我们来看一下这道题吧
线段树的单点修改啊，还不用建树！
（可是我没写出来23333【气死
然后谢谢题解
因为每次都在尾端插入
所以可以用st表来写
还是很好理解的思路
#include<cstdio> #include<algorithm> #include<cmath> #include<iostream> using namespace std; #define maxn 200010 int dp[maxn][21],cnt,b[maxn]; void add(int x){ dp[++ cnt][0] = x; for(int i = 1;cnt - (1 << i) >= 0;i++) dp[cnt][i] = max(dp[cnt][i - 1],dp[cnt - (1 << (i - 1))][i - 1]); } int query(int x){ int k = log2(cnt - x + 1); return max(dp[cnt][k],dp[x - 1 + (1 << k)][k]); } int main(){ int m,mod,last = 0; scanf("%d%d",&m,&mod); for(int i = 1;i <= m;i++){ char ch; cin >> ch; if(ch == 'A'){ int x; scanf("%d",&x); int qwq = (x + last) % mod; add(qwq); } else{ int y; scanf("%d",&y); int ans = query(cnt - y + 1); last = ans; printf("%d ",ans); } } return 0; }
每次写st表的时候都会忍不住想起zyr学长通俗易懂的st表讲解
tql！！！
（突然想起来还有作业【扔下水的一批的题解然后溜
在学长帮忙debug之后（orz谢谢
改了一下线段树写法
然后还没切掉
第二天再看的时候
（？？？我智障吗？？？
（为什么我改的时候还把‘A'的情况删掉了？？？
好吧
然后又写回来
过了【瘫
那看一下线段树的代码吧
#include<cstdio> #include<iostream> #include<algorithm> using namespace std; #define maxn 200010 int m,last,cnt,q; int node[maxn * 4];//emmm线段树需要开这么大www void modify(int orz,int qwq,int now,int L,int R) { if(L == R) { node[now] = qwq;//赋值 return ; } int mid = (L + R) >> 1; if(mid >= orz)//orz是当前加入的点的编号 modify(orz,qwq,now * 2,L,mid); if(mid < orz) modify(orz,qwq,now * 2 + 1,mid + 1,R); node[now] = max(node[now * 2],node[now * 2 + 1]) % q;//取最大 } int query(int l,int r,int now,int L,int R) {//询问操作，很好理解吧 if(l <= L && r >= R) return node[now]; if(l > R || r < L) return 0; int mid = (L + R) >> 1; return max(query(l,r,now * 2,L,mid),query(l,r,now * 2 + 1,mid + 1,R)); } int main() { scanf("%d %d",&m,&q); for(int i = 1; i <= m; i++) { char a; int b; cin >> a >> b; if(a == 'A'){ modify(++cnt,(b + last) % q,1,1,m); } if(a == 'Q') { last = query(cnt - b + 1,cnt,1,1,m) % q; printf("%d ",last); } } return 0; }
【痛哭流涕
【太不容易了嗷嗷嗷
然后放一下测评结果
上面的是线段树，下面是st表
