巷北

LCS:裸题直接上。

LCS2：拿每个串去匹配，得到每个结点的最大的答案。
对每个结点取每次匹配的最小值。同时用用每个结点更新pre
答案是每个结点答案去max

bzoj 2555：对每个np记1，然后暴力更新pre（强制在线= =）
然后询问，暴力匹配，失败就是0，成功就是这个点的sz(孩子包括自己的np个数)

bzoj 3988：T=0，每个结点记为1，求个子树和，多了下一位，不多向下（像主席树）
T=1，val[pre] += val[x]，同T=0

spojSUBLEX：同3998 T = 0

hdu3518：给代表主串的len个字符l=r=i，用x更新pre，相当于记录每个串的最早出现位置，最迟出现位置，如果每个点的r-l>pre.len，那么长度在min（r-l,lenx）到pre.len+1的之间的都可以成为答案。

hdu4436：多串的建立，每次新串就把last = root,插入一个结点时，如果必须要 !last[s[i]] || ch[last][s[i]] . len != i 才插入这个结点。然后做一遍树p就可以了。

hdu4416，拿每个串去跟主串匹配，求每个结点的max，用结点len键下就行，表示只有大于才不会出现重复

bzoj4032 http://jiruyi910387714.is-programmer.com/posts/90425.html

替罪羊套线段树 O(nlog^2n)

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<ctime>
#include<cmath>
using namespace std;

typedef pair<int, int> Pii;
typedef long long LL;
typedef long double db;
#define rep(_,A,B) for(_=A;_<=B;++_)
#define repi(_,A,B) for(register int _=A;_<=B;++_)
#define FOR(_,A) for(int _=h[A];_;_=next[_])
#define A first
#define B second
#define mp make_pair
char o;template<class O> void read(O&x){while(o=getchar(),o<'0'||o>'9');for(x=o^48;o=getchar(),o>='0'&&o<='9';)x=x*10+(o^48);}
const int L = 70005, M = 10000005;
const double alpha = 0.8;

int n, Q;
int a[L], id[L]; 

struct T { 
     int l, r, s;
     T(){ l = r = s = 0; }
}e[M];
#define mid (l + r >> 1)

int rec[M], rec_num, tot;

inline int newnode(void) {
    if(rec_num) { e[rec[rec_num]] = T(); return rec[rec_num--]; }
    else return ++tot;
}

void reclaim(int &x) {
     if(!x) return ;
     rec[++rec_num] = x; reclaim(e[x].l), reclaim(e[x].r);
}

void ins(int &x, int l, int r, int y, int f) {
     if(!x)x = newnode(); e[x].s += f;
     //cout << "ins : " << x << " " << l << " " << r << " " << y << endl;
     if(l == r) return ;
     if(y <= mid) ins(e[x].l, l, mid, y, f);
     else ins(e[x].r, mid + 1, r, y, f); 
     if(!e[x].s) reclaim(x), x = 0;
}

int root[L], lc[L], rc[L], Root;

void build(int &x, int l, int r) {
     //cout << "build " << l << " " << r << endl; 
     if(l > r) return ;
     x = id[mid];
     build(lc[x], l, mid - 1), build(rc[x], mid + 1, r);
     repi(i, l, r) ins(root[x], 0, 70000, a[id[i]], 1);//, cout << "INS " << x << " " << i << endl;
}

void init(void) {
     cin >> n;
     repi(i, 1, n) read(a[i]), id[i] = i;
     build(Root, 1, n);
}

int q[L], cnt;

void del(int &x) {
     //cout << "del " << x << endl;
     if(!x) return ; reclaim(root[x]), root[x] = 0;
     del(lc[x]); q[++cnt] = x; del(rc[x]); x = 0;
}

void rebuild(int &x) {
     //cout << "rebuild : " << x << endl;
     cnt = 0; del(x);
     repi(i, 1, cnt) id[i] = q[i];//, cout << id[i] << " "; cout << endl;   
     build(x, 1, cnt);
}

int tmp;

void ins(int &x, int y, int z) {
     //cout << "ins : " << x << " " << y << " " << z << endl;
     if(!x) { x = ++n, ins(root[x], 0, 70000, z, 1), a[x] = z; return ;}
     ins(root[x], 0, 70000, z, 1);
     int t = e[root[lc[x]]].s;
     if(y <= t) ins(lc[x], y, z);
     else ins(rc[x], y - t - 1, z);
     if(e[root[x]].s * alpha > max(e[root[lc[x]]].s, e[root[rc[x]]].s)) {
        if(tmp) {
          //cout << "rc2 " << rc[2] << endl;
          if(lc[x] == tmp) rebuild(lc[x]);
          else rebuild(rc[x]);
        }
        tmp = 0;
     }
     else tmp = x;
} 

int modify(int x, int y, int val) {
     ins(root[x], 0, 70000, val, 1); 
     //cout << "modify : " << x << " " << y << " " << val << endl;
     int z, t = e[root[lc[x]]].s;
     if(y <= t) z = modify(lc[x], y, val);
     else if(y - 1 == t)z = a[x], a[x] = val;
     else z = modify(rc[x], y - t - 1, val);
     ins(root[x], 0, 70000, z, -1);
     return z;
}

int q1[L], q2[L], cnt1, cnt2;

void query(int x, int l, int r) {
     //cout << "query " << x << " " << l << " " << r << " ";
     int l_s = e[root[lc[x]]].s, r_s = e[root[x]].s;  //cout << l_s << " " << r_s << endl;
     if(l == 1 && r == r_s) { q1[++cnt1] = root[x]; /*cout << "q1 " << x << endl;*/ return ; }
     if(l <= l_s + 1 && l_s + 1 <= r) q2[++cnt2] = a[x];//, cout << "q2 " << x << endl;
     if(r <= l_s) query(lc[x], l, r);
     else if(l > l_s + 1) query(rc[x], l - l_s - 1, r - l_s - 1);
     else {
        if(l <= l_s) query(lc[x], l, l_s);
        if(r > l_s + 1) query(rc[x], 1, r - l_s - 1);
     }
}

int Query(int x, int y, int k) {
    cnt1 = cnt2 = 0; query(Root, x, y);
    int l = 0, r = 70000;
    while(l < r) {
       int t = 0;
       repi(i, 1, cnt1) t += e[e[q1[i]].l].s;
       repi(i, 1, cnt2) if(l <= q2[i] && q2[i] <= mid) ++t;
       if(k <= t) {
         repi(i, 1, cnt1) q1[i] = e[q1[i]].l; r = mid;
       }
       else {
         repi(i, 1, cnt1) q1[i] = e[q1[i]].r; l = mid + 1, k -= t;
       }
    }
    return l;
}

void work(void) {
     cin >> Q;
     char op[5]; int x, y, k, ans = 0;
     while(Q--) {
        //cout << "Q rc2 " << Q + 1 << " " << rc[2] << endl;
        scanf("%s", op); read(x), read(y); x ^= ans, y ^= ans;
        if(op[0] == 'Q') read(k), printf("%d\n", ans = Query(x, y, k ^ ans));
        else if(op[0] == 'M') modify(Root, x, y);
        else tmp = 0, ins(Root, x - 1, y); 
     }
}
int main(void) {
  freopen("3065.in","r",stdin), freopen("3065.out","w",stdout);
  init(), work(); return 0;
}

对时间分治，用启发式并查集维护一下，时间复杂度O(mlog^2n)，然而并查集常数极小，所以跑的比lct的O(mlogn)还快。

lct见http://wuzuofan.is-programmer.com/posts/89928.html 或者 http://c-sunshine.logdown.com

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<ctime>
#include<cmath>
using namespace std;

typedef pair<int, int> Pii;
typedef long long LL;
typedef long double db;
#define rep(_,A,B) for(_=A;_<=B;++_)
#define repi(_,A,B) for(register int _=A;_<=B;++_)
#define FOR(_,A) for(int _=h[A];_;_=next[_])
#define A first
#define B second
#define mp make_pair
char o;template<class O> void read(O&x){while(o=getchar(),o<'0'||o>'9');for(x=o^48;o=getchar(),o>='0'&&o<='9';)x=x*10+(o^48);}
const int L = 100005, M = 200005;

int n, m, T;
struct M{ int u, v, st, ed; } e[M];
int fa[L], d[L], a[L], q[M], top; 

Pii findx(int x) {
    int t = 0;
    for(; fa[x] != x; x = fa[x]) t ^= a[x];
    return mp(x, t);
}

void merge(int x, int y, int dep) {
     if(d[x] > d[y]) swap(x, y);
     if(d[x] == d[y]) ++d[y], q[++top] = -y;
     fa[x] = y, a[x] = dep, q[++top] = x;
}

void resume(int t) {
     for(; top != t; --top)
       if(q[top] > 0) fa[q[top]] = q[top], a[q[top]] = 0;
       else --d[-q[top]];
}

void init(void) {
     cin >> n >> m >> T;
     repi(i, 1, m) {
       read(e[i].u), read(e[i].v), read(e[i].st), read(e[i].ed), ++e[i].st;
       if(e[i].st > e[i].ed) --m, --i;
     }
     repi(i, 1, n) fa[i] = i, d[i] = 1;
}

void solve(int l, int r, int r0) {
     int now = top, mid = l + r >> 1, i, j;
     rep(i, 1, r0) if(e[i].st <= l && r <= e[i].ed) {
         Pii x = findx(e[i].u), y = findx(e[i].v);
         int fx = x.A, fy = y.A, dep = !(x.B ^ y.B);
         if(fx != fy) merge(fx, fy, dep);
         else if(dep){ while(l <= r) puts("No"), ++l;  resume(now); return ; }
         swap(e[r0--], e[i--]);
     }
     if(l == r) { puts("Yes"); return ; }
     for(i = 1, j = r0; i <= j; ++i)
       if(e[i].st > mid) swap(e[i--], e[j--]);
     solve(l, mid, j);
     for(i = 1, j = r0; i <= j; ++i)
       if(e[i].ed <= mid) swap(e[i--], e[j--]);
     solve(mid + 1, r, j);
     resume(now);
}

void work(void) {
     solve(1, T, m); 
}
int main(void) {
  freopen("4025.in","r",stdin), freopen("4025.out","w",stdout);
  init(), work(); return 0;
}

orz cjy lzz wlp wzf

orz jzx nxy wyy