第一题 线段树

树状数组存差b[i] = a[i]-a[i-1]，反正是单点查询，我为什么没想到。。。很傻的用线段树

 

#include
     
      using namespace std;#define maxn 100005#define ll long long int n, m, a[maxn];struct SegmentTree{    struct node{        ll sum;        int lazy;     };    node Tree[maxn << 2];        #define ls l, m, v << 1    #define rs m+1, r, v << 1 | 1        void updata(int v){        Tree[v].sum = Tree[v << 1].sum + Tree[v << 1 | 1].sum;    }        void push_down(int l, int r, int v){        int m = (l + r) >> 1;        Tree[v << 1].sum += Tree[v].lazy * (m - l + 1) * 1LL;        Tree[v << 1].lazy += Tree[v].lazy;        Tree[v << 1 | 1].sum += Tree[v].lazy * (r - m) * 1LL;        Tree[v << 1 | 1].lazy += Tree[v].lazy;                Tree[v].lazy = 0;    }    void build(int l = 1, int r = n, int v = 1){        if(l == r) Tree[v].sum = a[l], Tree[v].lazy = 0;        else {            int m = (l + r) >> 1;            build(ls);            build(rs);            updata(v);        }    }        void modify(int x, int L, int R, int l = 1, int r = n, int v = 1){        if(l >= L && r <= R){            Tree[v].sum += x * (r - l + 1) * 1LL;            Tree[v].lazy += x;        }        else {            if(Tree[v].lazy) push_down(l, r, v);            int m = (l + r) >> 1;            if(L <= m)modify(x, L, R, ls);            if(R > m)modify(x, L, R, rs);            updata(v);        }    }        ll query(int x,int l = 1, int r = n, int v = 1){        if(l == r)return Tree[v].sum;        else {            if(Tree[v].lazy) push_down(l, r, v);            int m = (l + r) >> 1;            if(x <= m) return query(x, ls);            if(x > m)return query(x, rs);        }    }};SegmentTree Tr;int main(){    freopen("bit.in","r",stdin);    freopen("bit.out","w",stdout);    cin>>n;    for(int i = 1; i <= n; i++)scanf("%d", a + i);    Tr.build();    cin>>m;    for(int i = 1; i <= m; i++){        string opt;        cin>>opt;        if(opt[0] == 'm'){            int l, r, val;            scanf("%d%d%d",&l,&r,&val);            Tr.modify(val, l, r);        }        else {            int x;            scanf("%d",&x);            cout<
      
       <
      
     

 

第二题：一道巨恶心的线段树取模，一般公式知道了就没问题，但lazy乘起来是long long ,一堆人看了一晚上。。。第二天又忘了long long

 

#include
     
      using namespace std;#define maxn 100005#define ll long long int n, m, a[maxn];int mod = 1000000007;struct SegmentTree{    struct node{        ll sum,lazy[2];    };    node Tree[maxn << 2];        #define ls l, m, v << 1    #define rs m+1, r, v << 1 | 1        void updata(int v){        Tree[v].sum = ( Tree[v << 1].sum % mod + Tree[(v << 1) | 1].sum % mod ) % mod;            }        void push_down(int l, int r, int v){        if(Tree[v].lazy[0] == 1 && Tree[v].lazy[1] == 0)return;        int m = (l + r) >> 1;        int A = Tree[v].lazy[0], B = Tree[v].lazy[1];        modify(A, B, l, m, ls);        modify(A, B, m+1, r, rs);                Tree[v].lazy[0] = 1, Tree[v].lazy[1] = 0;    }    void build(int l = 1, int r = n, int v = 1){        if(l == r) Tree[v].sum = a[l], Tree[v].lazy[0] = 1, Tree[v].lazy[1] = 0;        else {            int m = (l + r) >> 1;            build(ls);            build(rs);            updata(v);            Tree[v].lazy[0] = 1, Tree[v].lazy[1] = 0;        }    }        void modify(int A, int B, int L, int R, int l = 1, int r = n, int v = 1){        if(l >= L && r <= R){            ll q = Tree[v].sum;            Tree[v].sum = (q * (A % mod) + 1LL * (B % mod) * (r - l + 1 )) % mod;            ll olda = Tree[v].lazy[0], oldb = Tree[v].lazy[1];            Tree[v].lazy[0] = A * olda % mod , Tree[v].lazy[1] = ( A * oldb + B )% mod;            //printf("olda = %d A = %d newa = %d\n",olda,A, Tree[v].lazy[0]);        }        else {            push_down(l, r, v);            int m = (l + r) >> 1;            if(L <= m)modify(A, B, L, R, ls);            if(R > m)modify(A, B, L, R, rs);            updata(v);        }            }        ll query(int L,int R,int l = 1, int r = n, int v = 1){        if(l >= L && r <= R)return Tree[v].sum ;        else {            push_down(l, r, v);            int m = (l + r) >> 1;            ll ans = 0;            if(L <= m) ans = (ans + query(L, R, ls) % mod) % mod;            if(R > m)ans = (ans % mod + query(L, R, rs)% mod) % mod;            return ans;        }    }};SegmentTree Tr;int main(){    freopen("linear.in","r",stdin);    freopen("linear.out","w",stdout);    cin>>n;    for(int i = 1; i <= n; i++)scanf("%d", a + i);    Tr.build();    cin>>m;    for(int i = 1; i <= m; i++){        string opt;        cin>>opt;        if(opt[0] == 'm'){            int l, r, A, B;            scanf("%d%d%d%d",&l,&r,&A,&B);            Tr.modify(A, B, l, r);                    }        else {            int l, r;            scanf("%d%d",&l,&r);            cout<
     

 

 

 

第三题 裸的splay扳子，很少找到卿学姐有这么接地气的板子，就搬过了，但splay的地方还是写挂了。。。

 

#include
     
      using namespace std;#define maxn 100005#define ll long long int n, m, a[maxn], val[maxn];struct SplayTree{    int siz[maxn], fa[maxn], son[maxn][2];    int tot, root;    void update(int nd){        siz[nd] = siz[son[nd][0]] + siz[son[nd][1]] + 1;    }    void init(){        siz[0] = 0;        tot = 0;        root = build(0, 1, n);    }    int build(int f, int l,int r){                if(l > r)return 0;        int nd = ++tot;        fa[nd] = f;        int m = (l + r) >> 1;        son[nd][0] = build(nd, l, m - 1);        son[nd][1] = build(nd, m + 1, r);        val[nd] = a[m];        update(nd);        //printf("nd = %d s[0] = %d, s[1] = %d, l = %d, r = %d val = %d\n",nd,son[nd][0],son[nd][1],l,r,val[nd]);        return nd;            }    int find(int pos){        int nd = root;        while(1){            int ls = siz[son[nd][0]];            if(pos <= ls)nd = son[nd][0];            else if(pos >= ls + 2){                pos -= ls + 1;                nd = son[nd][1];            }            else return nd;                    }    }    int query(int pos){        return val[find(pos)];    }    void rotate(int x,int d){        int y = fa[x];        son[y][d^1] = son[x][d];        if(son[x][d])fa[son[x][d]] = y;        fa[x] = fa[y];        if(fa[y]){            if(y == son[fa[y]][d])son[fa[y]][d] = x;            else son[fa[y]][d^1] = x;        }        son[x][d] = y, fa[y] = x;        update(y), update(x);    }    void splay(int x,int target = 0){        while(fa[x] != target){            int y = fa[x];            if(x == son[y][0]){                if(fa[y] != target && y == son[fa[y]][0])                    rotate(y, 1);                rotate(x, 1);            }            else {                if(fa[y] != target && y == son[fa[y]][1])                    rotate(y, 0);                rotate(x, 0);            }        }        if(!target)root = x;    }    void erase(int pos){        int lnd = find(pos - 1), rnd = find(pos + 1);        splay(lnd);        splay(rnd, lnd);        son[rnd][0] = 0;        update(rnd), update(lnd);    }};SplayTree Tr;int main(){    freopen("sequence.in","r",stdin);    freopen("sequence.out","w",stdout);    cin>>n>>m;    for(int i = 2; i <= n + 1; i++)scanf("%d", a + i);    a[1] = 0, a[n + 2] = 0;    n += 2;    Tr.init();        for(int i = 1; i <= m; i++){        string opt;        int pos;        cin>>opt;        scanf("%d",&pos);        if(opt[0] == 'D')Tr.erase(pos + 1);        else printf("%d\n",Tr.query(pos + 1));    }    }