[线段树] 洛谷P1198
程序员文章站
2022-03-22 13:12:26
...
题目
题目链接:https://www.luogu.com.cn/problemnew/solution/P1198
代码
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<cctype>
#include<ctime>
#include<iostream>
#include<string>
#include<map>
#include<queue>
#include<stack>
#include<set>
#include<vector>
#include<iomanip>
#include<list>
#include<bitset>
#include<sstream>
#include<fstream>
#include<complex>
#include<algorithm>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
#define int long long
using namespace std;
const int INF = 0x3f3f3f3f3f3f3f3f;
int tree[800010];
int mod;
void add(int s,int k,int o,int l,int r)
{
if(l==r)
{
tree[o]=k;
return;
}
int mid=(l+r)>>1;
if(mid>=s) add(s,k,o<<1,l,mid);
if(mid<s) add(s,k,o<<1|1,mid+1,r);
tree[o]=max(tree[o<<1],tree[o<<1|1])%mod;
}
int query(int ll,int rr,int o,int l,int r)
{
if(ll<=l&&rr>=r) return tree[o];
int mid=(l+r)>>1;
int a=-INF,b=-INF;
if(mid>=ll) a=query(ll,rr,o<<1,l,mid);
if(mid<rr) b=query(ll,rr,o<<1|1,mid+1,r);
return max(a,b);
}
int cnt,t; char s[2];int x;
signed main(){
//ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int n;
scanf("%lld%lld",&n,&mod);
memset(tree,0,sizeof tree);
int t1=n;
while(t1--){
scanf("%s %lld",s,&x);
if(s[0]=='A'){
add(cnt+1,(x+t)%mod,1,1,n);
cnt++;
// for(int i=1;i<=cnt;i++) printf("%lld\n",tree[i]);
}
if(s[0]=='Q'){
if(x==0) t=0;
else t=query(cnt-x+1,cnt,1,1,n)%mod;
//for(int i=1;i<=n*4;i++) printf("%lld\n",tree[i]);
// printf("")
printf("%lld\n",t);
}
}
return 0;
}
上一篇: LinkedList中的链表结构
推荐阅读
-
洛谷 P3366 【模板】最小生成树
-
洛谷P3380 【模板】二逼平衡树(树套树)
-
洛谷P4588 [TJOI2018]数学计算(线段树)
-
洛谷P3248 [HNOI2016]树(主席树 倍增 )
-
洛谷P3366 【模板】最小生成树(Boruvka算法)
-
洛谷P3120 [USACO15FEB]牛跳房子(动态开节点线段树)
-
洛谷P3313 [SDOI2014]旅行(树链剖分 动态开节点线段树)
-
洛谷P3960 列队(动态开节点线段树)
-
洛谷P3722 [AH2017/HNOI2017]影魔(线段树 set spaly)
-
洛谷P4383 [八省联考2018]林克卡特树lct(DP凸优化/wqs二分)