The Preliminary Contest for ICPC Asia Shanghai 2019 B题
线段树的样子，但基本在于区间修改，取异或，然后只查询一次
刚出炉的Shanghai网络赛
传送门
超内存版线段树
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#define lch(x) x<<1
#define rch(x) x<<1|1
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
const int MAXN=1e6+5;
int cover[MAXN<<2];
int sum[MAXN<<2];
inline int read(){//快读
char ch=getchar();int x=0,f=1;
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
void up(int rt){//更新本节点
sum[rt] = sum[lch(rt)] + sum[rch(rt)];
}
void down(int rt, int l, int r){
if(cover[rt]){
cover[lch(rt)] ^= 1;
cover[rch(rt)] ^= 1;
int m = (l + r) >> 1;
sum[lch(rt)] = m - l + 1 - sum[lch(rt)];
sum[rch(rt)] = r - m - sum[rch(rt)];
cover[rt] = 0;
}
}
void update(int L, int R, int l, int r, int rt){//更新
if(L <= l && R >= r){
cover[rt] ^= 1;
sum[rt] = r - l + 1 - sum[rt];
return;
}
down(rt, l, r);
int m = (l + r) >> 1;
if(L <= m) update(L, R, lson);
if(R > m) update(L, R, rson);
up(rt);
}
int query(int L, int R, int l, int r, int rt){
if(L <= l && R >= r) return sum[rt];
down(rt, l, r);
int m = (l + r) >> 1;
int ret = 0;
if(L <= m) ret += query(L, R, lson);
if(R > m) ret += query(L, R, rson);
return ret;
}
int main(){
int x;
x=read();
int n,m;
for(int k=1;k<=x;k++){
memset(cover,0,sizeof(cover));
memset(sum,0,sizeof(sum));
n=read(),m=read();
for(int i=0;i<m;i++){
int s,t;//更新区间[s,t]
s=read(),t=read();
update(s,t,1,n,1);
}
printf("Case #%d: ",k);
printf("%d
",query(1,n,1,n,1));
//printf("%d
",sum[1]);
}
return 0;
}
超时间版差分
既然超内存，想到线段树其实就是修改和查询
因为只查询一次，那么超内存的的话，用差分来减少内存
#include <iostream>
#include <cstdio>
#include <cstring>
#define rep(i,a,b) for(int i=a;i<b;i++)
using namespace std;
const int maxn=1e6+5;
int b[maxn];
int main(){
int t;
scanf("%d",&t);
for(int k=1;k<=t;k++){
int n,m;
scanf("%d%d",&n,&m);
//for(int i=0;i<=n+1;i++){
// b[i]=0;
//}
for(int i=1;i<=m;i++){
int l,r;
scanf("%d%d",&l,&r);
b[l]++;b[r+1]--;
}
int add=0;
int ans=0;
for(int i=1;i<=n;i++){
add+=b[i];
if(add%2==1)ans++;
b[i]=0;//自动清零
}
b[n+1]=0;
printf("Case #%d: %d
",k,ans);
}
return 0;
}
差分优化版
差分也需要遍历全部，导致时间复杂度高，所以重点在于减少差分的时间，用map优化，也就是离散化
/*
不能用线段树，爆内存，不能遍历n，o(t*n)，爆时间
差分思想+map容器
*/
#include <iostream>
#include <cstdio>
#include <map>
#define rep(i,a,b) for(int i=a;i<b;i++)
using namespace std;
map<int, int> mp;
inline int read(){//快读其实占内存的,正规比赛少用
char ch=getchar();int f=1,x=0;
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch<='9'&&ch>='0'){x+=x*10+ch-'0';ch=getchar();}
return x*f;
}
int main(){
int t;
//t=read();
scanf("%d",&t);
rep(i,1,t+1){
int n,m;
//n=read(),m=read();
scanf("%d%d",&n,&m);
rep(j,0,m){
int l,r;
//l=read(),r=read();
scanf("%d%d",&l,&r);
mp[l]++,mp[r+1]--;//差分
}
int t=0,p=0,ans=0;
map<int, int>::iterator it;
for(it=mp.begin();it!=mp.end();it++){
if(t%2!=0){//只对奇数进行
ans+=it->first-p;//有种离散化的感觉
}
p=it->first;
t+=it->second;
}
mp.clear();
printf("Case #%d: %d
",i,ans);
}
return 0;
}
区间传送门这题不能离散化因为就是O(t*n)的复杂度，还具有初始值，如果没有初始值，或者初始值都是一样的话，可以离散化