为什么同样一份代码不开 O2 能过,开了 O2 只有 80pts。
(语言换成 C++14
也是一样)
#include <bits/stdc++.h>
#define uint unsigned int
#define ls(x) t[x].l
#define rs(x) t[x].r
using namespace std;
namespace IO{
inline int read(){
int x = 0;
char ch = getchar();
while(!isdigit(ch)) ch = getchar();
while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
return x;
}
inline char readc(){
char ch = getchar();
while(ch < 'a' || ch > 'z') ch = getchar();
return ch;
}
template <typename T> inline void write(T x){
if(x > 9) write(x / 10);
putchar(x % 10 + '0');
}
}
using namespace IO;
const int N = 2e5 + 10;
int n, m;
uint fx[N], f[N];
char s[N], op[5];
struct fhq_treap{
int val, siz, wei, l, r;
uint sum;
}t[N];
int root, tot;
inline void pushup(int x){
t[x].siz = t[ls(x)].siz + t[rs(x)].siz + 1;
t[x].sum = t[ls(x)].sum * fx[t[rs(x)].siz + 1] + t[x].val * fx[t[rs(x)].siz] + t[rs(x)].sum;
}
inline void split(int x, int k, int &a, int &b){
if(!x) return a = b = 0, void();
if(k >= t[ls(x)].siz + 1) a = x, split(rs(x), k - t[ls(x)].siz - 1, rs(x), b);
else b = x, split(ls(x), k, a, ls(x));
pushup(x);
}
inline int merge(int x, int y){
if(!x || !y) return x | y;
if(t[x].wei <= t[y].wei){
rs(x) = merge(rs(x), y);
return pushup(x), x;
}else{
ls(y) = merge(x, ls(y));
return pushup(y), y;
}
}
inline int newnode(int k){
t[++tot].val = k, t[tot].siz = 1, t[tot].wei = rand(), t[tot].sum = k;
return tot;
}
inline void insert(int k, char ch){
// cout << "insert " << ch << endl;
int a, b;
split(root, k, a, b);
root = merge(merge(a, newnode(ch - 'a' + 1)), b);
}
inline void remove(int k){
int a, b, c;
split(root, k, a, b);
split(a, k - 1, a, c);
c = merge(ls(c), rs(c));
root = merge(merge(a, c), b);
}
inline void update(int x, char ch){
remove(x), insert(x - 1, ch);
}
inline uint calc(int l, int r){
int len = r - l + 1, a, b, c;
split(root, l - 1, a, b);
split(b, len, b, c);
uint res = t[b].sum;
root = merge(merge(a, b), c);
return res;
}
inline bool check(int l, int r, int len){
uint res1 = calc(l, l + len - 1), res2 = calc(r, r + len - 1);
return res1 == res2;
}
inline int query(int x, int y){
int l = 1, r = min(n - x, n - y) + 1, res;
while(l <= r){
int mid = (l + r) >> 1;
if(check(x, y, mid)) l = mid + 1, res = mid;
else r = mid - 1;
}
return res;
}
int main(){
scanf("%s", s + 1);
n = strlen(s + 1);
fx[0] = 1;
for(int i = 1; i < N; ++i) fx[i] = fx[i - 1] * 27;
for(int i = 1; i <= n; ++i) insert(i, s[i]);
m = read();
for(int i = 1; i <= m; ++i){
scanf("%s", op);
if(op[0] == 'Q'){
int x = read(), y = read();
write(query(x, y)), puts("");
}else if(op[0] == 'R'){
int x = read();
update(x, readc());
}else{
int x = read(); ++n;
insert(x, readc());
}
}
return 0;
}