偶然发现自己喜欢的code出了点瑕疵,写一篇分享帮其维护一下。嘻嘻~
import java.io.*;
public class Main{
static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
static int N = (int)2e5+10, m, p;
static node[] tr = new node[(int)8e5+10]; //线段树的点数需要开正常点数的4倍
public static int nextInt()throws IOException{
in.nextToken();
return (int)in.nval;
}
public static String Line()throws IOException{
in.nextToken();
return in.sval;
}
public static void build(int u, int l, int r){
tr[u] = new node(l, r, 0);
if(l==r) return; //如果区间不需要继续划分就结束递归
int mid = l+r>>1;
build(u<<1, l, mid); //建立左子树
build(u<<1|1, mid+1, r); //建立右子树
}
//求[l, r]区间的最大值,当前查询的节点编号为u
public static long query(int u, int l, int r){
if(l<=tr[u].l && tr[u].r<=r) return tr[u].v;
int mid = tr[u].l+tr[u].r>>1;
long v = 0;
if(l<=mid) v = Math.max(v, query(u<<1, l, r));
if(mid+1<=r) v = Math.max(v, query(u<<1|1, l, r));
return v;
}
//用子节点更新当前节点(没有递归,递归在modify里)
public static void pushup(int u){
tr[u].v = Math.max(tr[u<<1].v, tr[u<<1|1].v);
}
//单点修改(u是线段树的节点,x是区间的位置,v是修改的值)
public static void modify(int u, int x, long v){
if(tr[u].l == x && tr[u].r == x) tr[u].v = v;
else{
int mid = tr[u].l+tr[u].r>>1;
if(x<=mid) modify(u<<1, x, v);
if(mid+1<=x) modify(u<<1|1, x, v);
pushup(u); //每次修改完后都要用子节点更新当前节点
}
}
public static void main(String[] args)throws IOException{
m = nextInt(); p = nextInt();
build(1, 1, m); //建立根节点为1覆盖区间为[1, m]的线段树
int n = 0; //序列长度
long last = 0;
while(m-->0){
String op = Line();
int x = nextInt();
if(op.equals("Q")){
last = query(1, n-x+1, n); //这里的1代表从根结点开始查询
out.println(last);
}else{
modify(1 ,++n , (long)(last+x)%p);
}
}
out.flush();
out.close();
}
}
class node{
int l;
int r;
long v; //[l, r]区间的最大值
public node(int l, int r, long v){
this.l = l;
this.r = r;
this.v = v;
}
}