CQUPT 集训队专题训练（线段树）

线段树

链接

A - 敌兵布阵

题意

N个阵营，每个阵营有ai个士兵
在各个阵营的士兵不断变化的情况下快速查询[l,r]阵营中有多少士兵

思路

简单的线段树应用

AC代码

#include <iostream> 
#include <cstdio>
#include <cstdlib>
#include <cstring> 
#include <algorithm> 
using namespace std;
#define N 100005
int n, p[N];
char s[100];
int tree[N*4];

void build( int node , int begin , int end ){
    if( begin == end ){
        tree[node] = p[begin];
    }else{
        build( node * 2 , begin , (begin + end)/2 );
        build( node * 2 + 1, (begin + end) / 2 + 1 , end );

        tree[node] = tree[node * 2] + tree[node * 2 + 1];
    }
}

void updata( int node , int begin , int end , int ind , int add ){

    if( begin == end ){
        tree[node] += add;
        return;
    }

    int m = ( begin + end ) / 2;

    if( ind <= m ){
        updata( node * 2 , begin , m , ind , add );
    }else{
        updata( node * 2 + 1 , m+1 , end , ind , add );
    }

    tree[node] = tree[node*2] + tree[node*2+1];
}

int query( int node , int begin , int end , int qb , int qe ){
    int p1,p2;
    if( begin > qe || end < qb )
        return -1;

    if( begin >= qb && end <= qe ){
        return tree[node];
    }

    p1 = query( node * 2 , begin , ( begin + end ) / 2 , qb , qe );
    p2 = query( node * 2 + 1 , ( begin + end ) / 2 + 1 , end , qb , qe );

    if( p1 == -1 ){
        return p2;
    }else if( p2 == -1 ){
        return p1;
    }else{
        return p1 + p2;
    }
}

int main(){
    int t,c,d,cas = 1;
    memset(p,0,sizeof(p));
    memset(tree,0,sizeof(tree));
    scanf("%d",&t);
    while( t-- ){
        scanf("%d",&n);
        for( int i = 1 ; i <= n ; i++ ){
            scanf("%d",p+i);
        }
        build( 1 , 1 , n );
        printf("Case %d:\n",cas++);

        while( scanf("%s",s) != EOF && s[0] != 'E'){
            if( s[0] == 'A' ){
                scanf("%d%d",&c,&d);
                updata(1,1,n,c,d);
            }else if( s[0] == 'S' ){
                scanf("%d%d",&c,&d);
                updata(1,1,n,c,-1*d);
            }else if( s[0] == 'Q' ){
                scanf("%d%d",&c,&d);
                cout<<query( 1,1,n,c,d )<<endl;
            }
        }
    }
    return 0;
}

B - Color the ball

题意

N个气球排成一排，从左到右依次编号为1,2,3....N.每次给定2个整数a b(a <= b),lele便为骑上他的“小飞鸽"牌电动车从气球a开始到气球b依次给每个气球涂一次颜色。但是N次以后lele已经忘记了第I个气球已经涂过几次颜色了，你能帮他算出每个气球被涂过几次颜色吗？

思路

线段树区间更新，延时标记

AC代码

#include <iostream> 
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 100007

struct tr{
    int val;
    int mark;
};
struct tr tree[N*4];

void build(int node , int begin , int end){
    if( begin == end ){
        tree[node].val = 0;
        tree[node].mark = 0;
    }else{
        int mid = (begin+end)/2;
        build(node*2,begin,mid);
        build(node*2+1,mid+1,end);
        tree[node].val = 0;
        tree[node].mark = 0;
    }
}

void pushdown(int node,int begin,int end){
    if(begin == end)    return;
    if( tree[node].mark != 0 ){
        tree[node*2].mark += tree[node].mark;
        tree[node*2+1].mark += tree[node].mark;
        tree[node*2].val += tree[node].mark;
        tree[node*2+1].val += tree[node].mark;
        tree[node].mark = 0;
    }
}

void updata(int node, int begin , int end , int l , int r){
    if( l > end || r < begin )  return;
    if(l <= begin && r >= end){
        tree[node].val ++;
        tree[node].mark ++;
        return;
    }
    tree[node].val += tree[node].mark;;
    pushdown(node,begin,end);

    int mid = (begin+end)/2;
    updata(node*2,begin,mid,l,r);
    updata(node*2+1,mid+1,end,l,r);

}

int query(int node , int begin , int end , int l ){
    if(l > end || l < begin)    return 0;
    if( l <= begin && l >= end )    return tree[node].val;
    pushdown(node,begin,end);
    int mid = (begin + end) /2;
    if( l <= mid )  return query(node*2,begin,mid,l);
    else    return query(node*2+1,mid+1,end,l);
}

int main(){
    int n;
    while( scanf("%d",&n) != EOF && n ){
        build(1,1,n);
        int p,q;
        for(int i = 0 ; i < n ; i++){
            scanf("%d%d",&p,&q);
            updata(1,1,n,p,q);
        }
        printf("%d",query(1,1,n,1));
        for(int i = 2 ; i <= n ; i++){
            printf(" %d",query(1,1,n,i));
        }
        printf("\n");
    }
    return 0;
} 

C - Mayor's posters

题意

贴海报，每张海报宽都是1，贴的位置已知，顺序已知，海报长度已知
贴海报的黑板长已知
问最后能看见几张海报
只要露出一点也算能看见

思路

直接用线段树内存会炸
所以需要区间离散化
然后直接简单的线段树即可

AC代码

#include <iostream> 
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 20005
typedef long long LL;
int n,ans;

struct le{
    int begin,end;
};
le l[N];

struct lsh{
    int mask,val;
}; 
lsh s[N*3];

bool y[N*3];
int tree[N*4];

void cc(){
    ans = 0;
    memset(tree,0,sizeof(tree));
    memset(y,false,sizeof(y));
}

void build(int node , int begin , int end){
    tree[node] = 0;
    if(begin == end)
        return;
    int m = (begin+end)/2;
    build(node*2,begin,m);
    build(node*2+1,m+1,end);
}

void updata(int node,int begin , int end ,int qb , int qe , int add){
    //printf("node = %d , begin = %d ,end = %d , qb = %d , qe = %d , add = %d\n",node,begin,end,qb,qe,add);
    if( begin > qe || end < qb )
        return;
    if(begin>=qb&&end<=qe){
        tree[node] = add;
        return;
    }

    if(tree[node] > 0){
        tree[node*2+1] = tree[node*2] = tree[node];
        tree[node] = 0;
    }
    int m = (begin+end)/2;
    updata(node*2,begin,m,qb,qe,add);
    updata(node*2+1,m+1,end,qb,qe,add);
}

void query(int node , int begin , int end){
    //printf("node = %d\n",node);
    if(tree[node] > 0){
        if(!y[tree[node]]){
            y[tree[node]] = true;
            ans++;
        }
        return;
    }
    int m = (begin+end)/2;
    query(node*2,begin,m);
    query(node*2+1,m+1,end);
}


bool cmp(lsh a , lsh b){
    return a.val < b.val;
}

int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        cc();
        for(int i = 0 ; i < n ; i++){
            scanf("%d%d",&l[i].begin,&l[i].end);
            s[2*i].val = l[i].begin;
            s[2*i+1].val = l[i].end;
            s[2*i].mask = -(i+1);
            s[i*2+1].mask = i+1;
        }
        sort(s,s+2*n,cmp);
        int ac = s[0].val;
        int your_name = 1;
        for(int i = 0 ; i < 2*n ; i++){
            if( ac != s[i].val ){
                your_name++;
                ac = s[i].val;
            }

            if(s[i].mask < 0)
                l[-s[i].mask-1].begin = your_name;
            else
                l[s[i].mask-1].end = your_name;
        }

        build(1,1,your_name);
        for(int i = 0 ; i < n ; i++){
            updata(1,1,your_name,l[i].begin,l[i].end,i+1);
        }
        query(1,1,your_name);
        printf("%d\n",ans);
    }

    return 0;
}

D - Tunnel Warfare

题意

世界大战中，有好多城市被卷入
现在日本想要破坏我国领土
破坏城市已知，顺序已知
假定每座未被破坏的城市都与最近的两座城市联通
最近的城市被破坏则失联
规定任何被破坏的城市都与外界失联
每次修复只修复最后被破坏的城市
对于每次查询请给出当前城市的联通城市数目

思路

线段树先保存区间[begin,end]的最右边的联通区间[l,r]
则每次查询对于查询左边的分量采用简单的线段树查询
因为左边保存的为最右边的联通分量
当左边的右端点取到时继续查询右支的左端点联通区间即可
这是左支就不需要继续向下查询了
将查询到的区间合并就为最大联通区间
当为右支查询时，需要特判右支左端点是否能查询到
当可以查询到时才能合并左支右端点的最大联通区间
注意分支的时候查询的不是选来的参数，而是左右端点的联通区间

AC代码

#include <iostream> 
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 50007

struct tr{
    int left,right;
    bool d;
};

struct tr tree[N*8];
int dr[N];
int n,m;

void build(int node , int begin , int end){
    if(begin == end){
        tree[node].left = begin;
        tree[node].right = end;
        tree[node].d = false;
    }else{
        int m = (begin+end)/2;
        build(node*2,begin,m);
        build(node*2+1,m+1,end);
        tree[node].left = begin;
        tree[node].right = end;
        tree[node].d = false;
    }
}

void updata(int node,int begin , int end , int l , bool f){
    if(begin == end){
        if(f){
            tree[node].left = begin;
            tree[node].right = end;
            tree[node].d = false;
        }else{
            tree[node].left = 0;
            tree[node].right = 0;
            tree[node].d = true;
        }
    }else{
        int m =(begin+end)/2;
        if(l <= m)  updata(node*2,begin,m,l,f);
        else    updata(node*2+1,m+1,end,l,f);
        if(tree[node*2+1].d && tree[node*2].d){
            tree[node].d = true;
            tree[node].left = 0;
            tree[node].right = 0;
        }else if(tree[node*2].d){
            tree[node].d = false;
            tree[node].left = tree[node*2+1].left;
            tree[node].right = tree[node*2+1].right;
        }else if(tree[node*2+1].d ){
            tree[node].d = false;
            tree[node].left = tree[node*2].left;
            tree[node].right = tree[node*2].right;
        }else{
            tree[node].d = false;
            tree[node].right = tree[node*2+1].right;
            if( tree[node*2+1].left - tree[node*2].right == 1 )
                tree[node].left = tree[node*2].left;
            else
                tree[node].left = tree[node*2+1].left;
        }
    }
}

int ql , qr;
void query(int node , int begin , int end , int l){
    if( begin > l || end < l )  return;
    if( begin <= l && end >= l ){
        if( !tree[node].d ){
            if( tree[node].left <= l && tree[node].right >= l ){
                if( tree[node].right > qr ) qr = tree[node].right;
                if( tree[node].left < ql )  ql = tree[node].left;
            }else{
                int m = (begin+end)/2;
                if( l <= m  ){
                    query(node*2,begin,m,l);
                    if( qr == m && qr >= ql)
                        query(node*2+1,m+1,end,m+1);
                }else{
                    query(node*2+1,m+1,end,l);
                    if( ql == m+1  && qr >= ql){
                        query(node*2,begin,m,m);
                    }                   
                }       
            }
        }else{
            return;
        }
    }
}

void deal(char s[] , int *y){
    if( s[0] != 'R' ){
        (*y) = 0;
        int len = strlen(s);
        for(int i = 2 ; i < len && s[i] >= '0' && s[i] <= '9'; i++){
            (*y) *= 10;
            (*y) += s[i] - '0';
        }
    }
}

int main(){
    int y,drtop = -1;
    char j[100],x;
    while( scanf("%d%d",&n,&m) != EOF ){
        getchar();
        build(1,1,n);
        memset(dr,0,sizeof(dr));
        drtop = 0;
        for(int i = 0 ; i < m ; i++){
            memset(j,'\0',sizeof(j));
            gets(j);
            deal(j,&y);
            //printf("y = %d",y);
            if( j[0] != 'R' ){
                //scanf("%d",&y);
                if( j[0] == 'D' ){
                    //printf("here->1\n");
                    updata(1,1,n,y,false);
                    dr[++drtop] = y;
                }else if(j[0] == 'Q'){
                    //printf("here->2\n");
                    ql = y; qr = y-1;
                    query(1,1,n,y);
                    printf("%d\n",qr - ql + 1);
                }
            }else{
                if( drtop >= 0 ){
                    //printf("here->3\n");
                    updata(1,1,n,dr[drtop--],true);
                }
            }


        }
    }
    return 0;
}

E - A Simple Problem with Integers

题意

N个数
区间求和
区间变换

思路

简单的线段树区间更新即可
int:爆精度

AC代码

#include <iostream> 
#include <cstdio>
#include <cstdlib>
#include <cstring> 
#include <algorithm>
using namespace std;
#define N 100007
typedef long long LL;

int n,q,qa,qb,qv;
int p[N];
struct no{
    LL val;
    LL mark;
};
no tree[N*4];

void build(int node , int begin , int end){
    tree[node].mark = 0;
    if(begin == end){
        tree[node].val = (LL)p[begin];
        return;
    }else{
        int m = (begin + end) / 2;
        build(node*2,begin,m);
        build(node*2+1,m+1,end);
        tree[node].val = tree[node*2].val + tree[node*2+1].val;
    }
}

void pushdown(int node , int length){
    if(tree[node].mark != 0){
        tree[node*2].mark += tree[node].mark;
        tree[node*2+1].mark += tree[node].mark;
        tree[node*2].val += tree[node].mark * (length-length/2);
        tree[node*2+1].val += tree[node].mark * (length/2);
        tree[node].mark = 0;
    }
}

void updata(int node , int begin , int end , int qb , int qe , int add){
    if(qb<=begin&&qe>=end){
        tree[node].val += add * (end-begin+1);
        tree[node].mark += add;
        return;
    }
    pushdown(node,end-begin+1);
    int m = (begin + end)/2;
    if( qb <= m )
        updata(node*2,begin,m,qb,qe,add);
    if(qe > m)
        updata(node*2+1,m+1,end,qb,qe,add);
    tree[node].val = tree[node*2].val + tree[node*2+1].val;
}

LL query(int node , int begin , int end , int qb , int qe){
    if(qb <= begin && qe >= end)
        return tree[node].val;      
    pushdown(node,end-begin+1);
    int m = (begin+end)/2;
    LL ans = 0;
    if( qb <= m )
        ans += query(node*2,begin,m,qb,qe);
    if(qe > m)
        ans += query(node*2+1,m+1,end,qb,qe);
    return ans;
}

int main(){
    scanf("%d%d",&n,&q);
        for(int i = 1 ; i <= n ; i++){
            scanf("%d",p+i);
        }
        build(1,1,n);
        for(int i = 0 ; i < q ; i++){
            char ui[5];
            scanf("%s",ui);
            if( ui[0] == 'Q' ){
                scanf("%d%d",&qa,&qb);
                cout<<query(1,1,n,qa,qb)<<endl;
                //printf("%I64d\n",query(1,1,n,qa,qb));
            }else{
                //printf("here -> C>?\n");
                scanf("%d%d%d",&qa,&qb,&qv);
                updata(1,1,n,qa,qb,qv);
            }
        }
    return 0;
}

F - Sasha and Array

题意

N个数，a1,a2,a3,.....,an；
每次区间更新[l,r] 都加adc;
求区间[L,R]每一位对应分斐波拉契数列项的和
结果模1e9+7

思路

线段树延时标记
斐波拉契数列矩阵幂求法
快速矩阵幂
数的数据与延时标记均用斐波拉契数列项的二阶方阵存储
斐波拉契数列项和为左乘矩阵的和与[1 0]转置矩阵的乘积
当多项斐波拉契数列同时增加时相当于多项同时左乘一个矩阵
根据矩阵的运算性质可以将其左乘的矩阵提出，做延时标记
不是很懂为什么不用矩阵做延时会WA

AC代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 100007
typedef long long LL;
const LL MOD = 1e9+7;
LL p[N],n,m;
struct tr {
    LL ad[2][2];
    LL A[2][2];
};
tr tree[N*4];
const LL v[2] = {1,0};
const LL AC[2][2] = {1,1,1,0} , ADC[2][2] = {1,0,0,1};

void copyA(LL (*a)[2]) {
    for(int i = 0 ; i < 2 ; i++) {
        for(int k = 0 ; k < 2 ; k++) {
            a[i][k] = AC[i][k];
        }
    }
}

void copyADC(LL (*a)[2]) {
    for(int i = 0 ; i < 2 ; i++) {
        for(int k = 0 ; k < 2 ; k++) {
            a[i][k] = ADC[i][k];
        }
    }
}

void AcA(LL (*A)[2], LL (*B)[2] , LL (*ans)[2]) {
    LL C[2][2];
    C[0][0] = (A[0][0] * B[0][0] + A[0][1] * B[1][0])%MOD;
    C[0][1] = (A[0][0] * B[0][1] + A[0][1] * B[1][1])%MOD;
    C[1][0] = (A[1][0] * B[0][0] + A[1][1] * B[1][0])%MOD;
    C[1][1] = (A[1][0] * B[0][1] + A[1][1] * B[1][1])%MOD;
    for(int i = 0 ; i < 2 ; i++)    for(int k = 0 ; k < 2 ; k++)    ans[i][k] = C[i][k];
}

void ACA(LL (*A)[2],  LL ans[]) {
    ans[0] = A[0][0];
    ans[1] = A[1][0];
}

void Apows(LL (*A)[2] , int k) {
    if(k == 0) {
        A[0][0] = A[1][1] = 1;
        A[0][1] = A[1][0] = 0;
        return;
    }
    if( k <= 1) return;
    LL B[2][2];
    for(int i = 0 ; i < 2 ; i++)    for(int k = 0 ; k < 2 ; k++)    B[i][k] = A[i][k];
    if(k % 2 == 0) {
        AcA(A,A,A);
        Apows(A,k/2);
    } else {
        AcA(A,A,A);
        Apows(A,k/2);
        AcA(A,B,A);
    }
}

void Asum(LL (*A)[2], LL (*B)[2] , LL (*ans)[2]) {
    LL C[2][2];
    for(int i = 0 ; i < 2 ; i++)    for(int k = 0 ; k < 2 ; k++)    C[i][k] = (A[i][k] + B[i][k]) % MOD;
    for(int i = 0 ; i < 2 ; i++)    for(int k = 0 ; k < 2 ; k++)    ans[i][k] = C[i][k];
}

void build(int node , int begin , int end) {
    copyADC(tree[node].A);
    copyADC(tree[node].ad); 
    if(begin == end) {      
        LL pw[2][2];
        copyA(pw);
        Apows(pw,p[begin]-1);
        AcA(pw,tree[node].A,tree[node].A);
    } else {
        int m = (begin+end)/2;
        build(node*2,begin,m);
        build(node*2+1,m+1,end);        
        Asum(tree[node*2].A,tree[node*2+1].A,tree[node].A);
    }
}

void pushdown(int node, int begin , int end) {
    AcA(tree[node*2].A,tree[node].ad,tree[node*2].A);
    AcA(tree[node*2+1].A,tree[node].ad,tree[node*2+1].A);
    AcA(tree[node*2].ad,tree[node].ad,tree[node*2].ad);
    AcA(tree[node*2+1].ad,tree[node].ad,tree[node*2+1].ad);
    copyADC(tree[node].ad);
}

void updata(int node , int begin , int end , int l , int r ,LL (*pwe)[2]){
    if( l <= begin && r >= end ) {
        AcA(tree[node].A,pwe,tree[node].A);
        AcA(tree[node].ad,pwe,tree[node].ad);
        return;
    }
    pushdown(node,begin,end);
    int m = (begin+end)/2;
    if(l <= m)
        updata(node*2,begin,m,l,r,pwe);
    if(r > m)
        updata(node*2+1,m+1,end,l,r,pwe);
    Asum(tree[node*2].A,tree[node*2+1].A,tree[node].A);
}

LL query(int node,int begin , int end,int l,int r) {
    if( l <= begin && r >= end ) {
        return tree[node].A[0][0] % MOD;
    }
    pushdown(node,begin,end);
    int m = (begin+end)/2;
    LL p1 = 0,p2 = 0;
    if( l <= m )
        p1 = query(node*2,begin,m,l,r);
    if( r > m )
        p2 = query(node*2+1,m+1,end,l,r);
    return (p1+p2)%MOD;
}

int main() {
    int a,b,c;
    LL d;
    while( scanf("%lld%lld",&n,&m) != EOF ) {
        for(LL i = 1 ; i <= n ; i++)    scanf("%lld",p+i);
        build(1,1,n);
        for(int i = 0 ; i < m ; i++) {
            scanf("%d",&a);
            if( a == 1 ) {
                scanf("%d%d%lld",&b,&c,&d);
                LL pdf[2][2];
                copyA(pdf);
                Apows(pdf,d);
                updata(1,1,n,b,c,pdf);
            } else {
                scanf("%d%d",&b,&c);
                printf("%lld\n",query(1,1,n,b,c));
            }
        }
    }
    return 0;
}