inplace_merge函数(头文件#include)
举个例子，数组a在连续的lmid上是有序的，在mid+1r上是有序的，要把合并的话
表达如下
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.
",++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
",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
",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
*/