Visit Counter
AmazingCounters.com

1、题目大意:区间修改乘法操作和加法操作,求区间和
2、分析:为了填补bzoj2631的坑还是写一发题解吧,首先呢,既然想要双标记,但是这两个标记之间又有着制约作用,所以要定义优先级,这个优先级就定义为乘法先,加法后吧。。。那个一个区间的标记无非就是乘a加b,那么重点就是如何下传标记了。首先儿子有两个标记c,d,父亲有两个标记a,b, 那么c就等于c乘a啦,而d等于d乘a加b(从操作的先后顺序考虑)很显然吧。于是问题就解决了
3、代码:( 当时的线段树姿势丑陋,求轻喷

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
#define LL long long
struct segment_tree{
    LL N, P;
    LL sum[1000000];
    LL clazy[1000000];
    LL jlazy[1000000];
    LL value[1000000];
    LL x, y, z;
    void build(LL l, LL r, LL o){
        if(l == r){
            clazy[o] = 1;
            jlazy[o] = 0;
            sum[o] = value[l];
            return;
        }
        int mid = (l + r) / 2;
        build(l, mid, 2 * o);
        build(mid + 1, r, 2 * o + 1);
        sum[o] = sum[2 * o] + sum[2 * o + 1]; sum[o] %= P;
        clazy[o] = 1;
        jlazy[o] = 0;
        return;
    }
    void updata(LL l, LL r, LL o){
        clazy[2 * o] *= clazy[o]; clazy[2 * o] %= P;
        jlazy[2 * o] *= clazy[o]; jlazy[2 * o] %= P;
        jlazy[2 * o] += jlazy[o]; jlazy[2 * o] %= P;
        clazy[2 * o + 1] *= clazy[o]; clazy[2 * o + 1] %= P;
        jlazy[2 * o + 1] *= clazy[o]; jlazy[2 * o + 1] %= P;
        jlazy[2 * o + 1] += jlazy[o]; jlazy[2 * o + 1] %= P;
        sum[o] = sum[o] * clazy[o] + jlazy[o] * (r - l + 1); sum[o] %= P;
        clazy[o] = 1;
        jlazy[o] = 0;
        return;
    }
    void add_c(LL l, LL r, LL o){
        updata(l, r, o);
        if(x > r || y < l) return;
        if(x <= l && r <= y){
            clazy[o] = z;
            updata(l, r, o);
            return;
        }
        LL mid = (l + r) / 2;
        add_c(l, mid, 2 * o);
        add_c(mid + 1, r, 2 * o + 1);
        sum[o] = sum[2 * o] + sum[2 * o + 1]; sum[o] %= P;
        return;
    }
    void add_j(LL l, LL r, LL o){
        updata(l, r, o);
        if(x > r || y < l) return;
        if(x <= l && r <= y){
            jlazy[o] = z;
            updata(l, r, o);
            return;
        }
        LL mid = (l + r) / 2;
        add_j(l, mid, 2 * o);
        add_j(mid + 1, r, 2 * o + 1);
        sum[o] = sum[2 * o] + sum[2 * o + 1]; sum[o] %= P;
        return;
    }
    LL query(LL l, LL r, LL o){
        updata(l, r, o);
        if(x > r || y < l) return 0;
        if(x <= l && r <= y) return sum[o];
        LL mid = (l + r) / 2;
        LL ret = 0;
        ret += query(l, mid, 2 * o); ret %= P;
        ret += query(mid + 1, r, 2 * o + 1); ret %= P;
        sum[o] = sum[2 * o] + sum[2 * o + 1]; sum[o] %= P;
        return ret; 
    }
} wt;
int main(){
    scanf("%lld%lld", &wt.N, &wt.P);
    for(LL i = 1; i <= wt.N; i ++){
        scanf("%lld", &wt.value[i]);
    }
    wt.build(1, wt.N, 1);
    LL q;
    scanf("%lld", &q);
    while(q --){
        LL a;
        scanf("%lld", &a);
        if(a == 1){
            scanf("%lld%lld%lld", &wt.x, &wt.y, &wt.z);
            wt.add_c(1, wt.N, 1);
        }
        else if(a == 2){
            scanf("%lld%lld%lld", &wt.x, &wt.y, &wt.z);
            wt.add_j(1, wt.N, 1);
        }
        else if(a == 3){
            scanf("%lld%lld", &wt.x, &wt.y);
            printf("%lld\n", wt.query(1, wt.N, 1));
        }
    }
    return 0;
} 

1、题目大意:bzoj1798的lct版本
2、分析:这个把线段树改成splay就好
3、代码:

#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
#define LL long long
namespace LinkCutTree{
    struct Node{
        Node *ch[2], *fa;
        LL sum, num;
        LL size;
        bool rev;
        LL mul, plu; 
         
        inline int which();
         
        inline void reverse(){
            if(this) rev ^= 1;
        }
         
        inline void pd();
         
        inline void maintain(){
            sum = (num + ch[0] -> sum + ch[1] -> sum) % 51061;
            size = (1 + ch[0] -> size + ch[1] -> size) % 51061;
        }
         
        Node();
    } *null = new Node, tree[100010], *pos[100010];
     
    Node::Node(){
        num = sum = 1;
        rev = false;
        ch[0] = ch[1] = fa = null;
        mul = 1;
        plu = 0;
        size = 1;
    }
     
    inline void Node::pd(){
            if(rev){
                swap(ch[0], ch[1]);
                ch[0] -> reverse();
                ch[1] -> reverse();
                rev = false;
            }
            if(ch[0] != null){
                ch[0] -> mul *= mul;
                ch[0] -> plu *= mul;
                ch[0] -> plu += plu;
                ch[0] -> num *= mul;
                ch[0] -> num += plu; 
                ch[0] -> sum *= mul;
                ch[0] -> sum += plu * ch[0] -> size;
                ch[0] -> mul %= 51061;
                ch[0] -> plu %= 51061;
                ch[0] -> num %= 51061;
                ch[0] -> sum %= 51061; 
            }
            if(ch[1] != null){
                ch[1] -> mul *= mul;
                ch[1] -> plu *= mul;
                ch[1] -> plu += plu;
                ch[1] -> num *= mul;
                ch[1] -> num += plu; 
                ch[1] -> sum *= mul;
                ch[1] -> sum += plu * ch[1] -> size;
                ch[1] -> mul %= 51061;
                ch[1] -> plu %= 51061;
                ch[1] -> num %= 51061;
                ch[1] -> sum %= 51061;
            }
            mul = 1;
            plu = 0;
    }
     
    inline int Node::which(){
        if(fa == null || (this != fa -> ch[0] && this != fa -> ch[1])) return -1;
        return this == fa -> ch[1];
    }
     
    inline void rotate(Node *o){
        Node *p = o -> fa;
        int l = o -> which(), r = l ^ 1;
        o -> fa = p -> fa;
        if(p -> which() != -1) p -> fa -> ch[p -> which()] = o;
        p -> ch[l] = o -> ch[r];
        if(o -> ch[r]) o -> ch[r] -> fa = p;
        o -> ch[r] = p; p -> fa = o;
        o -> ch[r] -> maintain();
        o -> maintain();
    }
     
    inline void splay(Node *o){
        static stack<Node*> st;
        if(!o) return;
        Node *p = o;
        while(1){
            st.push(p);
            if(p -> which() == -1) break;
            p = p -> fa;
        }
        while(!st.empty()){
            st.top() -> pd(); st.pop();
        }
         
        while(o -> which() != -1){
            p = o -> fa;
            if(p -> which() != -1){
                if(p -> which() ^ o -> which()) rotate(o);
                else rotate(p);
            }
            rotate(o);
        }
    }
     
    inline void Access(Node *o){
        Node *y = null;
        while(o != null){
            splay(o);
            o -> ch[1] = y;
            o -> maintain();
            y = o; o = o -> fa;
        }
    }
     
    inline void MovetoRoot(Node *o){
        Access(o);
        splay(o);
        o -> reverse();
    }
     
    inline Node* FindRoot(Node *o){
        Access(o);
        splay(o);
        while(o -> ch[0] != null) o = o -> ch[0];
        return o;
    }
     
    inline void Link(Node *x, Node *y){
        MovetoRoot(x);
        x -> fa = y;
    }
     
    inline void Cut(Node *x, Node *y){
        MovetoRoot(x);
        Access(y);
        splay(y);
        y -> ch[0] = x -> fa = null;
        y -> maintain();
    }
}
int main(){
    using namespace LinkCutTree;
    null -> mul = 1;
    null -> size = 0;
    null -> plu = 0;
    null -> sum = 0;
    null -> num = 0;
    null -> ch[0] = null -> ch[1] = null -> fa = NULL;
    int n, q;
    scanf("%d%d", &n, &q);
    for(int i = 1; i <= n; i ++) pos[i] = &tree[i];
    for(int i = 1; i < n; i ++){
        int u, v;
        scanf("%d%d", &u, &v);
        Link(pos[u], pos[v]);
    }
    char op[5];
    int x1, y1, x2, y2, c;
    while(q --){
        scanf("%s", op);
        if(op[0] == '+'){
            scanf("%d%d%d", &x1, &y1, &c);
            MovetoRoot(pos[x1]);
            Access(pos[y1]);
            splay(pos[y1]);
            pos[y1] -> num += c;
            pos[y1] -> num %= 51061;
            pos[y1] -> sum += pos[y1] -> size * c;
            pos[y1] -> sum %= 51061;
            pos[y1] -> plu += c;
            pos[y1] -> plu %= 51061;
        }
        else if(op[0] == '-'){
            scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
            Cut(pos[x1], pos[y1]);
            Link(pos[x2], pos[y2]);
        }
        else if(op[0] == '*'){
            scanf("%d%d%d", &x1, &y1, &c);
            MovetoRoot(pos[x1]);
            Access(pos[y1]);
            splay(pos[y1]);
            pos[y1] -> num *= c;
            pos[y1] -> num %= 51061;
            pos[y1] -> sum *= c;
            pos[y1] -> sum %= 51061;
            pos[y1] -> mul *= c;
            pos[y1] -> mul %= 51061;
            pos[y1] -> plu *= c;
            pos[y1] -> plu %= 51061;
        }
        else{
            scanf("%d%d", &x1, &y1);
            MovetoRoot(pos[x1]);
            Access(pos[y1]);
            splay(pos[y1]);
            pos[y1] -> sum %= 51061;
            printf("%lld\n", pos[y1] -> sum);
        }
    }
    return 0;
}

1、题目大意:动态树问题,点修改,链查询xor和
2、分析:太裸了
3、代码:

#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
namespace LinkCutTree{
    struct Node{
        Node *ch[2], *fa;
        int sum, num;
        bool rev;
         
        inline int which();
         
        inline void reverse(){
            if(this) rev ^= 1;
        }
         
        inline void pd(){
            if(rev){
                swap(ch[0], ch[1]);
                ch[0] -> reverse();
                ch[1] -> reverse();
                rev = false;
            }
        }
         
        inline void maintain(){
            sum = num ^ ch[0] -> sum ^ ch[1] -> sum;
        }
         
        Node();
    } *null = new Node, tree[300010], *pos[300010];
     
    Node::Node(){
        num = sum = 0;
        rev = false;
        ch[0] = ch[1] = fa = null;
    }
     
    inline int Node::which(){
        if(fa == null || (this != fa -> ch[0] && this != fa -> ch[1])) return -1;
        return this == fa -> ch[1];
    }
     
    inline void rotate(Node *o){
        Node *p = o -> fa;
        int l = o -> which(), r = l ^ 1;
        o -> fa = p -> fa;
        if(p -> which() != -1) p -> fa -> ch[p -> which()] = o;
        p -> ch[l] = o -> ch[r];
        if(o -> ch[r]) o -> ch[r] -> fa = p;
        o -> ch[r] = p; p -> fa = o;
        o -> ch[r] -> maintain();
        o -> maintain();
    }
     
    inline void splay(Node *o){
        static stack<Node*> st;
        if(!o) return;
        Node *p = o;
        while(1){
            st.push(p);
            if(p -> which() == -1) break;
            p = p -> fa;
        }
        while(!st.empty()){
            st.top() -> pd(); st.pop();
        }
         
        while(o -> which() != -1){
            p = o -> fa;
            if(p -> which() != -1){
                if(p -> which() ^ o -> which()) rotate(o);
                else rotate(p);
            }
            rotate(o);
        }
    }
     
    inline void Access(Node *o){
        Node *y = null;
        while(o != null){
            splay(o);
            o -> ch[1] = y;
            o -> maintain();
            y = o; o = o -> fa;
        }
    }
     
    inline void MovetoRoot(Node *o){
        Access(o);
        splay(o);
        o -> reverse();
    }
     
    inline Node* FindRoot(Node *o){
        Access(o);
        splay(o);
        while(o -> ch[0] != null) o = o -> ch[0];
        return o;
    }
     
    inline void Link(Node *x, Node *y){
        MovetoRoot(x);
        x -> fa = y;
    }
     
    inline void Cut(Node *x, Node *y){
        MovetoRoot(x);
        Access(y);
        splay(y);
        y -> ch[0] = x -> fa = null;
        y -> maintain();
    }
}
int main(){
    using namespace LinkCutTree;
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++){
        int x; scanf("%d", &x);
        pos[i] = &tree[i];
        pos[i] -> num = pos[i] -> sum = x;
    }
    int op, x, y;
    while(m --){
        scanf("%d%d%d", &op, &x, &y);
        if(op == 0){
            MovetoRoot(pos[x]);
            Access(pos[y]);
            splay(pos[y]);
            printf("%d\n", pos[y] -> sum);
        }
        else if(op == 1){
            if(FindRoot(pos[x]) != FindRoot(pos[y])) Link(pos[x], pos[y]);
        } 
        else if(op == 2){
            if(FindRoot(pos[x]) == FindRoot(pos[y])) Cut(pos[x], pos[y]);
        }
        else{
            Access(pos[x]);
            splay(pos[x]);
            pos[x] -> num = y;
            pos[x] -> maintain();
        }
    }
    return 0;
}

1、题目大意:动态树问题,点修改,链查询。另外说明双倍经验题=bzoj1180
2、分析:lct模板题,练手的
3、代码:

#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
namespace LinkCutTree{
    struct Node{
        Node *ch[2], *fa;
        int sum, num;
        bool rev;
         
        inline int which();
         
        inline void reverse(){
            if(this) rev ^= 1;
        }
         
        inline void pd(){
            if(rev){
                swap(ch[0], ch[1]);
                ch[0] -> reverse();
                ch[1] -> reverse();
                rev = false;
            }
        }
         
        inline void maintain(){
            sum = num + ch[0] -> sum + ch[1] -> sum;
        }
         
        Node();
    } *null = new Node, tree[30010], *pos[30010];
     
    Node::Node(){
        num = sum = 0;
        rev = false;
        ch[0] = ch[1] = fa = null;
    }
     
    inline int Node::which(){
        if(fa == null || (this != fa -> ch[0] && this != fa -> ch[1])) return -1;
        return this == fa -> ch[1];
    }
     
    inline void rotate(Node *o){
        Node *p = o -> fa;
        int l = o -> which(), r = l ^ 1;
        o -> fa = p -> fa;
        if(p -> which() != -1) p -> fa -> ch[p -> which()] = o;
        p -> ch[l] = o -> ch[r];
        if(o -> ch[r]) o -> ch[r] -> fa = p;
        o -> ch[r] = p; p -> fa = o;
        o -> ch[r] -> maintain();
        o -> maintain();
    }
     
    inline void splay(Node *o){
        static stack<Node*> st;
        if(!o) return;
        Node *p = o;
        while(1){
            st.push(p);
            if(p -> which() == -1) break;
            p = p -> fa;
        }
        while(!st.empty()){
            st.top() -> pd(); st.pop();
        }
         
        while(o -> which() != -1){
            p = o -> fa;
            if(p -> which() != -1){
                if(p -> which() ^ o -> which()) rotate(o);
                else rotate(p);
            }
            rotate(o);
        }
    }
     
    inline void Access(Node *o){
        Node *y = null;
        while(o != null){
            splay(o);
            o -> ch[1] = y;
            o -> maintain();
            y = o; o = o -> fa;
        }
    }
     
    inline void MovetoRoot(Node *o){
        Access(o);
        splay(o);
        o -> reverse();
    }
     
    inline Node* FindRoot(Node *o){
        Access(o);
        splay(o);
        while(o -> ch[0] != null) o = o -> ch[0];
        return o;
    }
     
    inline void Link(Node *x, Node *y){
        MovetoRoot(x);
        x -> fa = y;
    }
     
    inline void Cut(Node *x, Node *y){
        MovetoRoot(x);
        Access(y);
        splay(y);
        y -> ch[0] = x -> fa = null;
        y -> maintain();
    }
}
int main(){
    using namespace LinkCutTree;
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++){
        int x; scanf("%d", &x);
        pos[i] = &tree[i];
        pos[i] -> sum = pos[i] -> num = x;
    }
    int m;
    scanf("%d", &m);
    char op[20];
    int x, y;
    for(int i = 1; i <= m; i ++){
        scanf("%s%d%d", op, &x, &y);
        if(op[0] == 'b'){
            if(FindRoot(pos[x]) != FindRoot(pos[y])){
                puts("yes");
                Link(pos[x], pos[y]);
            }
            else puts("no");
        }
        else if(op[0] == 'p'){
            Access(pos[x]);
            splay(pos[x]);
            pos[x] -> num = y;
            pos[x] -> maintain();
        }
        else{
            if(FindRoot(pos[x]) != FindRoot(pos[y])) puts("impossible");
            else{
                MovetoRoot(pos[x]);
                Access(pos[y]);
                splay(pos[y]);
                printf("%d\n", pos[y] -> sum);
            }
        }
    }
    return 0;
}

1、 题目大意:一篇论文是由许多单词组成,现在想知道每个单词分别在论文中出现多少次。
2、分析:对着 广义后缀自动机的图看,我们就会发现玄机,答案不就是这个单词下的后缀个数吗?
于是建立自动机,然后求出right,统计答案就好
3、代码:

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
struct SAM{
    struct node{
        int tranc[27], fa, len, right;
    } a[2002010];
    int c[2002010], od[2002010];
    int cnt, tail;
    SAM(){
        tail = ++ cnt;
    }
    void insert(int k){
        int p, np = ++ cnt, q, nq;
        a[np].len = a[tail].len + 1;
        a[np].right = 1;
        for(p = tail; p && !a[p].tranc[k]; p = a[p].fa) a[p].tranc[k] = np;
        if(!p) a[np].fa = 1;
        else{
            q = a[p].tranc[k];
            if(a[q].len == a[p].len + 1) a[np].fa = q;
            else{
                a[nq = ++ cnt] = a[q];
                a[q].fa = a[np].fa = nq;
                a[nq].len = a[p].len + 1;
                a[nq].right = 0;
                for(; a[p].tranc[k] == q; p = a[p].fa) a[p].tranc[k] = nq;
            }
        }
        tail = np;
    }
    void init(int m){
        for(int i = 1; i <= cnt; i ++) c[a[i].len] ++;
        for(int i = 1; i <= m; i ++) c[i] += c[i - 1];
        for(int i = cnt; i >= 1; i --) od[c[a[i].len] --] = i;
        for(int i = cnt; i >= 1; i --){
            int x = od[i];
            a[a[x].fa].right+=a[x].right;
        }
        return;
    }
} sam;
char str[2000100];
int tot;
int main(){
    int n;
    scanf("%d", &n);
    tot = -1;
    for(int i = 1; i <= n; i ++){
        char ch = getchar();
        while(ch < 'a' || ch > 'z') ch = getchar();
        while('a' <= ch && ch <= 'z'){
            str[++ tot] = ch;
            ch = getchar(); 
        }
        str[++ tot] = 'z'+1;
    }
    tot ++; 
    for(int i = 0; i < tot; i ++) sam.insert(str[i] - 'a');
    sam.init(tot);
    int num;
    int o = 0;
    for(int i = 1; i <= n; i ++){
        int now = 1, j; 
        for(j = o; ((int)str[j] != 'z'+1) && (j < tot); j ++){
            now = sam.a[now].tranc[str[j]-'a'];
        }
        o = j + 1;
        printf("%d\n", sam.a[now].right);
    }
    return 0;
}


1、题目大意:给一个序列,给一些询问,求区间最大值和最小值
2、分析: 懒得脑补st表 ,直接线段树裸上
3、代码:

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
int qmin[200010], qmax[200010]; 
int a[200010];
int getint(){
    char ch = getchar(); int x = 0, f = 1;
    while(ch < '0' || ch > '9'){
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while('0' <= ch && ch <= '9'){
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}
inline void build(int l, int r, int o){
    if(l == r){
        qmin[o] = qmax[o] = a[l];
        return;
    }
    int mid = (l + r) / 2;
    build(l, mid, 2 * o);
    build(mid + 1, r, 2 * o + 1);
    qmin[o] = min(qmin[2 * o], qmin[2 * o + 1]);
    qmax[o] = max(qmax[2 * o], qmax[2 * o + 1]);
    return; 
}
inline int query_min(int l, int r, int o, int x, int y){
    if(x <= l && r <= y){
        return qmin[o];
    }
    int mid = (l + r) / 2;
    int res = 2147483647;
    if(x <= mid) res = min(res, query_min(l, mid, 2 * o, x, y));
    if(y > mid) res = min(res, query_min(mid + 1, r, 2 * o + 1, x, y));
    return res;
}
inline int query_max(int l, int r, int o, int x, int y){
    if(x <= l && r <= y){
        return qmax[o];
    }
    int mid = (l + r) / 2;
    int res = 0;
    if(x <= mid) res = max(res, query_max(l, mid, 2 * o, x, y));
    if(y > mid) res = max(res, query_max(mid + 1, r, 2 * o + 1, x, y));
    return res;
}
int main(){
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);
    build(1, n, 1);
    for(int i = 1; i <= m; i ++){
        int l, r;
        scanf("%d%d", &l, &r);
        printf("%d\n", query_max(1, n, 1, l, r) - query_min(1, n, 1, l, r));
    }
    return 0;
}

1、题目大意: 就是给一个n×m的方格,然后一些平面上的 求和 修改操作
2、分析:二维树状数组裸题
3、代码:

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
int C[110][310][310];
int a[310][310];
int n, m;
inline void add(int c, int x, int y, int z){
    for(; x <= n; x += (x & -x)){
        int yy = y;
        for(; yy <= m; yy += (yy & -yy)){
            C[c][x][yy] += z;
        }
    }
    return;
}
inline int query(int c, int x, int y){
    int res = 0;
    for(; x > 0; x -= (x & -x)){
        int yy = y;
        for(; yy > 0; yy -= (yy & -yy)){
            res += C[c][x][yy];
        }
    }
    return res;
}
int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++){
        for(int j = 1; j <= m; j ++){
            int c; scanf("%d", &c);
            add(c, i, j, 1); a[i][j] = c;
        }
    }
    int Q;
    scanf("%d", &Q);
    while(Q --){
        int op, x1, y1, x2, y2, c;
        scanf("%d", &op);
        if(op == 1){
            scanf("%d%d%d", &x1, &y1, &c);
            add(a[x1][y1], x1, y1, -1);
            add(c, x1, y1, 1);
            a[x1][y1] = c;
        }
        else{
            scanf("%d%d%d%d%d", &x1, &x2, &y1, &y2, &c);
            printf("%d\n", query(c, x2, y2) - query(c, x1 - 1, y2) - query(c, x2, y1 - 1) + query(c, x1 - 1, y1 - 1));
        }
    }
    return 0;
} 

1、题目大意:求末尾L个数的最大值,强制在线
2、分析:这个拿线段树可以直接水过,然后我写了一个 维护单调栈, 二分求最大值的短代码,手懒。。。。
3、代码:

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
#define LL long long
pair<LL, LL> a[1000000];
LL tot;
int main(){
    LL M, D;
    scanf("%lld%lld", &M, &D);
    LL ans = 0;
    LL cnt = 0;
    while(M --){
        char str[2];
        LL d;
        scanf("%s%lld", str, &d);
        if(str[0] == 'A'){
            d += ans;
            d %= D;
            cnt ++;
            while(tot >= 1 && a[tot].second < d) tot --;
            a[++ tot].first = cnt;
            a[tot].second = d;
        }
        else{
            d = (cnt - d + 1);
            LL l = 1, r = tot;
            while(l < r){
                LL mid = (l + r) / 2;
                if(a[mid].first < d) l = mid + 1;
                else r = mid;
            }
            ans = a[l].second;
            printf("%lld\n", ans);
        }
    }
    return 0;
} 

1、题目大意:就是一个动态维护森林联通性的题
2、分析:lct模板题( 边界卡死了
3、代码:

#include <stack> 
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
#define LL long long
#define eps 1e-7
int n, m;
namespace LinkCutTree{
    struct Node{
        Node *ch[2], *fa;
        bool rev;
        Node(){
            ch[0] = ch[1] = NULL;
            fa = NULL;
            rev = false;
        } 
         
        inline int which(){
            if(fa == NULL || (fa -> ch[0] != this && fa -> ch[1] != this)) return -1;
            return fa -> ch[1] == this;
        }
         
        inline bool reverse(){
            if(this) rev ^= 1;
        }
         
        inline void pd(){
            if(rev){
                swap(ch[0], ch[1]);
                if(ch[0] != NULL) ch[0] -> reverse();
                if(ch[1] != NULL) ch[1] -> reverse();
                rev = false;
            }
        } 
    } ft[10010], *pos[10010];
   
    inline void rotate(Node *o){
        Node *p = o -> fa;
        int l = o -> which(), r = l ^ 1;
        o -> fa = p -> fa;
        if(p -> which() != -1) p -> fa -> ch[p -> which()] = o;
        p -> ch[l] = o -> ch[r];
        if(o -> ch[r]) o -> ch[r] -> fa = p;
        o -> ch[r] = p; p -> fa = o;
    } 
     
    inline void splay(Node* o){
        static stack<Node*> st;
        if(!o) return;
        Node* p = o;
        while(1){
            st.push(p);
            if(p -> which() == -1) break;
            p = p -> fa;
        }
        while(!st.empty()){
            st.top() -> pd(); st.pop();
        }
         
        while(o -> which() != -1){
            p = o -> fa;
            if(p -> which() != -1){
                if(p -> which() ^ o -> which()) rotate(o);
                else rotate(p);
            }
            rotate(o);
        }
    }
     
    inline void Access(Node* o){
        Node* p = NULL;
        while(o != NULL){
            splay(o);
            o -> ch[1] = p;
            p = o; o = o -> fa;
        }
    }
     
    inline void MovetoRoot(Node* o){
        Access(o);
        splay(o);
        o -> reverse();
    }
     
    inline Node* FindRoot(Node* o){
        while(o -> fa != NULL){
            o = o -> fa;
        }
        return o;
    } 
     
    inline void Link(Node* x, Node* y){
        MovetoRoot(x);
        x -> fa = y;
    }
     
    inline void Cut(Node* x, Node* y){
        MovetoRoot(x);
        Access(y);
        splay(y);
        x -> fa = NULL;
        y -> ch[0] = NULL;
    }
     
    inline void init(){
        for(int i = 1; i <= n; i ++) pos[i] = &ft[i];
    }
     
    inline void Connect(int u, int v){
        Link(pos[u], pos[v]);
    }
     
    inline void Destroy(int u, int v){
        Cut(pos[u], pos[v]);
    }
     
    inline bool Query(int u, int v){
        return FindRoot(pos[u]) == FindRoot(pos[v]);
    }
}
 
int main(){
    char op[10];
    int u, v;
    scanf("%d%d", &n, &m);
    LinkCutTree::init();
    for(int i = 1; i <= m; i ++){
        scanf("%s", op);
        scanf("%d%d", &u, &v);
        if(op[0] == 'C') LinkCutTree::Connect(u, v);
        else if(op[0] == 'D') LinkCutTree::Destroy(u, v);
        else puts(LinkCutTree::Query(u, v) ? "Yes" : "No"); 
    }
    return 0;
}