inplace_merge函数(头文件#include)

举个例子，数组a在连续的l~mid上是有序的，在mid+1~r上是有序的，要把合并的话
表达如下

inplace_merge(a+l,a+mid+1,a+r+1);

线段树题目

十分钟敲了一道线段树

/*

1
10
2
1 5 2
5 9 3
*/ 
/*
reference:
    
translation:
    
solution:

trigger:
    
note:
    *注意：是修改成某个值而不是加上某个值 ，注意f函数 
record:

date:
    2019.09.04
*/
#define N 100010

#define lson o<<1
#define rson o<<1|1

int n,k,tot;

struct tree{
    int l,r;
    int add,sum;
}t[N<<2];

inline void pushup(int o){
    t[o].sum=t[lson].sum+t[rson].sum;
}

inline void f(int delta,int o){
    t[o].add=delta;
    t[o].sum=delta*(t[o].r-t[o].l+1); 
}

inline void pushdown(int o){
    if(t[o].add==0)return ;
    f(t[o].add,lson);
    f(t[o].add,rson);
    t[o].add=0;
}

inline void change(int o,int x,int y,int v){
    if(x<=t[o].l && t[o].r<=y){
        f(v,o);
        return ;
    }
    pushdown(o);
    int mid=t[o].l+t[o].r>>1;
    if(x<=mid)change(lson,x,y,v);
    if(mid<y)change(rson,x,y,v);
    pushup(o);
}

inline int query(int o,int x,int y){
    if(x<=t[o].l && t[o].r<=y){
        return t[o].sum;
    }
    pushdown(o);
    int mid=t[o].l+t[o].r>>1;
    int ans=0;
    if(x<=mid)ans+=query(lson,x,y);
    if(mid<y)ans+=query(rson,x,y);
    return ans;
}

inline void build(int l,int r,int o){
    t[o].l=l,t[o].r=r;
    if(l==r){
        t[o].sum=1;
        return ;
    }
    int mid=l+r>>1;
    build(l,mid,lson);
    build(mid+1,r,rson);
    pushup(o);
}

#undef int
int main(){
#define int long long
    #ifdef WIN32
    freopen("1698.txt","r",stdin);
    #endif
    int T;rd(T);
    while(T--){
        //初始化 
        mem(t,0);
        rd(n),rd(k);
        build(1,n,1);
        while(k--){
            int x,y,z;rd(x),rd(y),rd(z);
            change(1,x,y,z);
        }
        printf("Case %lld: The total value of the hook is %lld.\n",++tot,query(1,1,n));
    }
    return 0;
}

离散化+线段树 贴海报

reference

/*
reference:
    
translation:
    
solution:

trigger:
    
note:
    *
record:

date:
    2019.09.04
*/
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define dwn(i,a,b) for(int i=a;i>=b;--i) 
template <typename T> inline void rd(T &x){x=0;char c=getchar();int f=0;while(!isdigit(c)){f|=c=='-';c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}x=f?-x:x;} 
inline void write(int n){if(n==0)return;write(n/10);putchar(n%10+'0');}
#define mem(a,b) memset(a,b,sizeof(a))
#define ee(i,u) for(int i=head[u];i;i=e[i].next)

#define N 10010
#define M 20010

#define lson o<<1
#define rson o<<1|1
int ans=0;
struct tree{
    int l,r;
}a[N<<2]; 

bool vis[M<<2];
struct node{
    int l,r;
    int val;
}t[M<<2];

int b[M<<2],n,tot=0,x,y;

int init(){//读入并进行离散处理
    rd(n);
    tot=0;
    rep(i,1,n){
        rd(a[i].l),rd(a[i].r);
        b[++tot]=a[i].l;
        b[++tot]=a[i].r;
        b[++tot]=a[i].r+1;
    }
    sort(b+1,b+tot+1);
    int len=unique(b+1,b+tot+1)-b-1;
    rep(i,1,n){
        a[i].l=lower_bound(b+1,b+len+1,a[i].l)-b;
        a[i].r=lower_bound(b+1,b+len+1,a[i].r)-b;;
    }
    return len; //离散化后总共处理多长的墙; 
}

inline void pushup(int o){
    t[lson].val=t[rson].val=t[o].val;
}

void pushdown(int o){
    if(t[o].val==-1)return ;
    pushup(o);
    t[o].val=-1;
}

inline void build(int o,int l,int r){
    t[o].l=l,t[o].r=r;
    t[o].val=0;
    if(l==r){
        return ;
    }
    int mid=t[o].l+t[o].r>>1;
    build(lson,l,mid);
    build(rson,mid+1,r);
}

void updata(int o,int x,int y,int v){
    if(x<=t[o].l && t[o].r<=y){
        t[o].val = v;
        return;
    }
    pushdown(o);
    int mid=t[o].l+t[o].r>>1;
    if(x<=mid)updata(lson,x,y,v);
    if(mid<y)updata(rson,x,y,v);
}

void query(int o,int x,int y){
    if(t[o].val!=-1){
         if(!vis[t[o].val]){
            vis[t[o].val] = 1;//做标记
            ++ans;
         }
        return;
    }
    query(lson,x,y);
    query(rson,x,y);
}

int ask(int x,int y){
    mem(vis,0);
    ans=0;
    vis[0]=1;
    query(1,x,y);
    return ans;
}

int main(){
    #ifdef WIN32
    freopen("poster.txt","r",stdin);
    #endif
    int T;rd(T);
    while(T--){
        mem(a,0),mem(t,0);
        int m=init();   
        tot=0;//海报染成的颜色
        build(1,1,m);
        rep(i,1,n)
            updata(1,a[i].l,a[i].r,++tot);
        printf("%d\n",ask(1,m));
    }
    return 0;
}

poj2155 刘汝佳 线段树思考题

  //#include <bits/stdc++.h>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctype.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define dwn(i,a,b) for(int i=a;i>=b;--i) 
template <typename T> inline void rd(T &x){x=0;char c=getchar();int f=0;while(!isdigit(c)){f|=c=='-';c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}x=f?-x:x;} 
inline void write(int n){if(n==0)return;write(n/10);putchar(n%10+'0');}
#define mem(a,b) memset(a,b,sizeof(a))
#define ee(i,u) for(int i=head[u];i;i=e[i].next)
 
#define N 1010
#define lowbit(i) (-i)&i

int tr[N][N];

inline void update(int x,int y){
    for(int i=x;i<=N;i+=lowbit(i))
        for(int j=y;j<=N;j+=lowbit(j))
            tr[i][j]^=1;
}

inline int query(int x,int y){
    int ans=0;
    for(int i=x;i;i-=lowbit(i))
        for(int j=y;j;j-=lowbit(j))
            ans^=tr[i][j];
    return ans;
}

int main(){
    int T;rd(T);
    while(T--){
        mem(tr,0);//智娃记得初始化 
        int n,t;rd(n),rd(t);
        while(t--){
            char op[3];
            scanf("%s",op);
            if(op[0]=='Q'){
                int x,y;rd(x),rd(y);
                printf("%d\n",query(x,y));
            }
            else if(op[0]=='C'){
                int x,y,p,q;
                rd(x),rd(y),rd(p),rd(q);
                update(x,y);
                update(p+1,y);
                update(x,q+1);
                update(p+1,q+1);
            }
        }
        puts("");
    }
    return 0;
}
/*
1
2 10
C 2 1 2 2
Q 2 2
C 2 1 2 1
Q 1 1
C 1 1 2 1
C 1 2 1 2
C 1 1 2 2
Q 1 1
C 1 1 2 1
Q 2 1
*/
/*
1
0 
0
1
*/

9.4

原文：https://www.cnblogs.com/sjsjsj-minus-Si/p/11634768.html