后缀平衡树的模板题？ I'm so weak……
现在觉得替罪羊树比 treap 好写，是不是没救了喵～
#include <cstdio>
#include <cmath>
typedef unsigned long long LL;
const double a=0.55;
const LL inf=1ULL<<;
const int sizeOfString=;
const int sizeOfTree=; inline int getint();
inline char getch();
inline int getstr(char * );
inline void putint(int); int n, q, len, type;
char s[sizeOfString];
int P[sizeOfString];
inline void reverse(); struct node {int p, s; LL tag; node * c[];};
node memory_node[sizeOfString], * port_node=memory_node;
node * root;
node * suf[sizeOfString];
inline node * newnode(int);
inline bool cmp(int, int);
inline bool cmp(node * , node * );
node * flatten(node * , node * );
node * build(node * , int);
void print(node * );
void rebuild(node *& );
void remark(node * , LL, LL);
bool insert(node *& , node * , LL=, LL=inf, int=); struct seg {int p; seg * l, * r;};
seg memory_seg[sizeOfTree], * port_seg=memory_seg;
seg * t;
inline seg * newseg();
inline int min(int, int);
seg * build(int, int);
void update(seg * , int, int, int);
int query(seg * , int, int, int, int); int main()
{
int ans=;
char ch;
int c, x, pos, l, r; n=getint(), q=getint(), len=getint(), type=getint();
getstr(s);
reverse(); root=suf[]=newnode();
root->tag=(+inf)>>;
for (int i=;i<=len;i++)
{
suf[i]=newnode(i);
insert(root, suf[i]);
} for (int i=;i<=n;i++) P[i]=getint(); t=build(, n);
for (int i=;i<=q;i++)
{
ch=getch();
if (ch=='I')
{
c=getint(); if (type) c=c^ans;
s[++len]=c+'a';
suf[len]=newnode(len);
insert(root, suf[len]);
}
if (ch=='C')
{
x=getint(); pos=getint();
P[x]=pos;
update(t, , n, x);
}
if (ch=='Q')
{
l=getint(); r=getint();
ans=query(t, , n, l, r);
putint(ans);
}
} return ;
}
inline int getint()
{
register int num=;
register char ch;
do ch=getchar(); while (ch<'' || ch>'');
do num=num*+ch-'', ch=getchar(); while (ch>='' && ch<='');
return num;
}
inline char getch()
{
register char ch;
do ch=getchar(); while (ch!='I' && ch!='C' && ch!='Q');
return ch;
}
inline int getstr(char * str)
{
register int len=;
register char ch;
do ch=getchar(); while (ch<'a' || ch>'z');
do str[++len]=ch, ch=getchar(); while (ch>='a' && ch<='z');
return len;
}
inline void putint(int num)
{
char stack[];
register int top=;
for ( ;num;num/=) stack[++top]=num%+'';
for ( ;top;top--) putchar(stack[top]);
putchar('\n');
}
inline void reverse()
{
static char t[sizeOfString];
for (int i=;i<=len;i++) t[i]=s[len-i+];
for (int i=;i<=len;i++) s[i]=t[i];
}
inline node * newnode(int p)
{
node * ret=port_node++;
ret->p=p; ret->s=;
ret->tag=0LL;
ret->c[]=NULL; ret->c[]=NULL;
return ret;
}
inline bool cmp(int a, int b)
{
return suf[a]->tag<suf[b]->tag;
}
inline bool cmp(node * a, node * b)
{
return s[a->p]==s[b->p]?cmp(a->p-, b->p-):s[a->p]<s[b->p];
}
node * flatten(node * x, node * y)
{
if (!x) return y;
x->c[]=flatten(x->c[], y);
return flatten(x->c[], x);
}
node * build(node * x, int s)
{
node * y, * z;
if (!s) return x->c[]=NULL, x;
y=build(x, s>>); z=build(y->c[], s--(s>>));
y->c[]=z->c[]; z->c[]=y;
return z;
}
void rebuild(node *& t)
{
static node temp;
node * line;
int n=t->s;
line=flatten(t, &temp);
build(line, n);
t=temp.c[];
}
void remark(node * t, LL l, LL r)
{
LL m=(l+r)>>;
t->tag=m; t->s=;
if (t->c[]) remark(t->c[], l, m), t->s+=t->c[]->s;
if (t->c[]) remark(t->c[], m, r), t->s+=t->c[]->s;
}
bool insert(node *& t, node * x, LL l, LL r, int d)
{
LL m=(l+r)>>;
bool ret=false;
if (!t) x->tag=m, t=x, ret=d>(log(root->s)/log(1.0/a));
else
{
t->s++;
if (cmp(t, x)) ret=insert(t->c[], x, m, r, d+);
else ret=insert(t->c[], x, l, m, d+);
if (ret) if ((t->c[] && t->c[]->s>a*t->s) || (t->c[] && t->c[]->s>a*t->s))
{
rebuild(t);
remark(t, l, r);
ret=false;
}
}
return ret;
}
inline seg * newseg()
{
seg * ret=port_seg++;
ret->l=ret->r=NULL;
return ret;
}
inline int min(int x, int y)
{
if (suf[P[x]]->tag<=suf[P[y]]->tag) return x;
return y;
}
seg * build(int l, int r)
{
seg * t=newseg();
if (l==r) return t->p=l, t;
int m=(l+r)>>;
t->l=build(l, m); t->r=build(m+, r);
t->p=min(t->l->p, t->r->p);
return t;
}
void update(seg * t, int l, int r, int p)
{
if (l==r) return ;
int m=(l+r)>>;
if (p<=m) update(t->l, l, m, p);
else update(t->r, m+, r, p);
t->p=min(t->l->p, t->r->p);
}
int query(seg * t, int l, int r, int ql, int qr)
{
if (l==ql && r==qr) return t->p;
int m=(l+r)>>;
if (qr<=m) return query(t->l, l, m, ql, qr);
else if (ql>=m+) return query(t->r, m+, r, ql, qr);
return min(query(t->l, l, m, ql, m), query(t->r, m+, r, m+, qr));
}
又 RE 又 WA 一时爽
到最后也没有搞清楚 zkw 炸在哪里……
大概是 zkw 查询时并不是顺序的缘故？