https://www.luogu.org/problem/show?pid=1198
之前刚学完Splay想找题练手的时候做的，写完Splay交上去了才发现这应该是线段树裸题23333
Splay解法
按照要求操作即可……
#include <iostream>
using namespace std;
int m, d, t;
const int inf = 0x7fffffff;
namespace splay
{
struct node;
node *nil = , *root;
struct node
{
int val, size, maxnum;
node *ch[];
node(int v) : val(v), size(), maxnum(v)
{
ch[] = ch[] = nil;
}
void pull_up()
{
size = ch[]->size + ch[]->size + ;
maxnum = max(val, max(ch[]->maxnum, ch[]->maxnum));
}
int cmp(int k)
{
if(this == nil || k == ch[]->size + )
return -;
else
return (k <= ch[]->size) ? : ;
}
};
void init()
{
if(!nil)
nil = new node(-inf);
nil->size = ;
nil->ch[] = nil->ch[] = nil;
root = new node(-inf);
root->ch[] = new node(-inf);
root->size = ;
}
void rotate(node *&t, int d)
{
node *k = t->ch[d ^ ];
t->ch[d ^ ] = k->ch[d];
k->ch[d] = t;
t->pull_up();
k->pull_up();
t = k;
}
void splay(int k, node *&t = root)
{
int d1 = t->cmp(k);
if(d1 == )
k = k - t->ch[]->size - ;
if(d1 != -)
{
int d2 = t->ch[d1]->cmp(k);
if(d2 != -)
{
int k2 = (d2 == ) ? (k - t->ch[d1]->ch[]->size - ) : k;
splay(k2, t->ch[d1]->ch[d2]);
if(d1 != d2)
{
rotate(t->ch[d1], d2 ^ );
rotate(t, d1 ^ );
}
else
{
rotate(t, d1 ^ );
rotate(t, d2 ^ );
}
}
else
rotate(t, d1 ^ );
}
}
void insert(int val)
{
splay(root->size - );
node *k = root->ch[];
root->ch[] = new node(val);
root->ch[]->ch[] = k;
k->pull_up();
root->ch[]->pull_up();
root->pull_up();
}
int get_maxnum(int len)
{
int from = root->size - len;
int to = from + len - ;
splay(to + , root);
splay(from - , root->ch[]);
return root->ch[]->ch[]->maxnum;
}
}
int main()
{
using namespace splay;
cin >> m >> d;
init();
char a;
int b;
while(m--)
{
cin >> a >> b;
switch(a)
{
case 'A':
insert((b + t) % d);
break;
case 'Q':
t = get_maxnum(b);
cout << t << endl;
break;
}
}
return ;
}
线段树解法
M<=2e5，也就是极限状况下最多2e5个数。开个长度是2e5的线段树，再记录下已经加了N个数了。每次插入就是更改第N+1个元素，查询就是查询区间[N-L+1,N]的最大值。
懒得重写一遍了……