我承认，比赛的时候在C题上卡了好久（最后也不会），15min水掉D后（最后还FST了。。），看到E时已经只剩15min了。尽管一眼看出是离散化+线段树的裸题，但是没有时间写，实在尴尬。
赛后先照习惯码出线段树，提交上去WA4？？？看了好久没看出问题，怎么调都不对。这时TJW忽悠我：“我写的可持久化线段树啊，不用离散化了啊。”我信了，码出主席树（实话说确实不用想那么多了，无脑动态开点就行了），提交上去TLE18？？？回头一问TJW：“我FST了啊。”我：（
不过TJW还是提供了一个非常有用的信息：像这道题的离散化线段树，可以将区间左端点与（区间右端点+1）进行离散化，然后线段树写左闭右开的（碰巧我就是这么写的），这样避免了很多麻烦。我原本的处理方法是将左右端点以及它们的下一位都塞进去离散化，虽然也没有问题，但是空间翻了倍。
回头重新调线段树，结果秒发现问题：我在main函数中调用线段树时参数用的是离散化的下标，结果线段树里我又把下标转回了未离散化的下标：（，实在是画蛇添足。。
/* Codeforces 915E Physical Education Lessons
1st Edition:2018.1.15 Monday
Algorithm:HJT Tree
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#include <deque>
#include <stack>
#include <iomanip>
#include <cstdlib>
#include <ctime>
#include <cctype>
using namespace std; #define is_lower(c) (c>='a' && c<='z')
#define is_upper(c) (c>='A' && c<='Z')
#define is_alpha(c) (is_lower(c) || is_upper(c))
#define is_digit(c) (c>='0' && c<='9')
#define stop system("PAUSE")
#define ForG(a,b,c) for(int (a)=c.head[b];(a);(a)=c.E[a].nxt)
#define For(a,b,c) for(int (a)=(b);(a)<=(c);++a)
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define shl(x,y) ((x)<<(y))
#define shr(x,y) ((x)>>(y))
#define mp make_pair
#define pb push_back
#ifdef ONLINE_JUDGE
#define hash rename_hash
#define next rename_next
#define prev rename_prev
#endif
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef double db;
const ll inf=2000000007LL;
const double EPS=1e-;
const ll inf_ll=(ll)1e18;
const ll maxn=300005LL;
const ll mod=1000000007LL; int n,q; struct HJT_Tree{
struct node{
int ch[],l,r;
int set,sum;
node():l(),r(),set(-),sum(){ch[]=ch[]=;}
node(int nl,int nr):l(nl),r(nr),set(-),sum(){ch[]=ch[]=;}
}T[maxn<<];
int size,root;
#define lch(u) T[u].ch[0]
#define rch(u) T[u].ch[1] inline print_node(int u){printf("[%d] %d %d %d %d\n",u,T[u].l,T[u].r,T[u].set,T[u].sum);}
inline int new_node(int l,int r){
T[++size]=node(l,r);
return size;
}
inline void set_node(int u,int val){
T[u].set=val;
T[u].sum=(T[u].r-T[u].l)*val;
}
inline void init(){
root=;
For(i,,size) T[i]=node();
T[]=node(,n+);
size=;
}
inline void push_up(int u){
T[u].sum=T[lch(u)].sum+T[rch(u)].sum;
}
inline void append(int u){
int nl=T[u].l,nr=T[u].r,mid=(nl+nr)>>;
if(!lch(u)) lch(u)=new_node(nl,mid);
if(!rch(u)) rch(u)=new_node(mid,nr);
}
inline void push_down(int u){
append(u);
if(T[u].set>=){
set_node(lch(u),T[u].set);set_node(rch(u),T[u].set);
T[u].set=-;
}
}
void _modify(int &u,int nl,int nr,int l,int r,int val){
if(nl>=r || nr<=l) return;
// print_node(u);
if(nl>=l && nr<=r){set_node(u,val);return;}
push_down(u);
int mid=(nl+nr)>>;
_modify(lch(u),nl,mid,l,r,val);_modify(rch(u),mid,nr,l,r,val);
push_up(u);
}
inline void modify(int l,int r,int val){_modify(root,,n+,l,r+,val);}
int _query(int &u,int nl,int nr,int l,int r){
if(nl>=r || nr<=l) return ;
if(nl>=l && nr<=r) return T[u].sum;
push_down(u);
int mid=(nl+nr)>>;
return _query(lch(u),nl,mid,l,r)+_query(rch(u),mid,nr,l,r);
}
inline int query(int l,int r){return _query(root,,n+,l,r+);}
#undef lch
#undef rch
}HJT; int main(){
scanf("%d%d",&n,&q);
HJT.init();
HJT.modify(,n,);
while(q--){
int x,y,opt;
scanf("%d%d%d",&x,&y,&opt);
if(opt^) HJT.modify(x,y,);
else HJT.modify(x,y,);
printf("%d\n",HJT.query(,n+));
}
return ;
} /*
4
6
1 2 1
3 4 1
2 3 2
1 3 2
2 4 1
1 4 2 */
先贴上主席树的代码
/* Codeforces 915E Physical Education Lessons
1st Edition:2018.1.14 Sunday
2nd Edition:2018.1.16 Tuesday
Algorithm:Interval Tree,Hash
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#include <deque>
#include <stack>
#include <iomanip>
#include <cstdlib>
#include <ctime>
#include <cctype>
using namespace std; #define is_lower(c) (c>='a' && c<='z')
#define is_upper(c) (c>='A' && c<='Z')
#define is_alpha(c) (is_lower(c) || is_upper(c))
#define is_digit(c) (c>='0' && c<='9')
#define stop system("PAUSE")
#define ForG(a,b,c) for(int (a)=c.head[b];(a);(a)=c.E[a].nxt)
#define For(a,b,c) for(int (a)=(b);(a)<=(c);++a)
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define shl(x,y) ((x)<<(y))
#define shr(x,y) ((x)>>(y))
#define mp make_pair
#define pb push_back
#ifdef ONLINE_JUDGE
#define hash rename_hash
#define next rename_next
#define prev rename_prev
#endif
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef double db;
const ll inf=2000000007LL;
const double EPS=1e-;
const ll inf_ll=(ll)1e18;
const ll maxn=300005LL;
const ll mod=1000000007LL; int n,q;
int l[maxn],r[maxn],opt[maxn];
vi Hash; struct Interval_Tree{
struct node{
int l,r,sum,set,size;
node(){}
node(int nl,int nr):l(nl),r(nr),set(-),size(),sum(){}
}T[maxn<<];
#define lch(u) (u<<1)
#define rch(u) (u<<1|1) inline void push_up(int u){
T[u].sum=T[lch(u)].sum+T[rch(u)].sum;
}
inline void set_node(int u,int val){
T[u].set=val;
T[u].sum=val*T[u].size;
}
inline void push_down(int u){
if(T[u].set>=){
set_node(lch(u),T[u].set);set_node(rch(u),T[u].set);
T[u].set=-;
}
}
void _build(int u,int l,int r){
T[u]=node(l,r);
if(l==r-){
T[u].size=Hash[r]-Hash[l];
set_node(u,);
return;
}
_build(lch(u),l,(l+r)>>);_build(rch(u),(l+r)>>,r);
push_up(u);
T[u].size=T[lch(u)].size+T[rch(u)].size;
}
inline void build(int size){
_build(,,size);
}
void _modify_set(int u,int l,int r,int val){
int nl=T[u].l,nr=T[u].r;
if(nl>=l && nr<=r){set_node(u,val);return;}
if(nl>=r || nr<=l) return;
push_down(u);
_modify_set(lch(u),l,r,val);_modify_set(rch(u),l,r,val);
push_up(u);
}
inline void modify_set(int l,int r,int val){
_modify_set(,l,r,val); //这里本来写的是_modify_set(1,Hash[l],Hash[r],val);
}
int _query_sum(int u,int l,int r){
int nl=T[u].l,nr=T[u].r;
if(nl>=l && nr<=r) return T[u].sum;
if(nl>=r || nr<=l) return ;
push_down(u);
return _query_sum(lch(u),l,r)+_query_sum(rch(u),l,r);
}
inline int query_sum(int l,int r){
return _query_sum(,l,r); //这里同理。。
}
inline void print_node(int u){
printf("[%d] %d %d %d %d %d\n",u,T[u].l,T[u].r,T[u].size,T[u].sum,T[u].set);
}
void _print(int u){
int nl=T[u].l,nr=T[u].r;
print_node(u);
if(nl==nr-) return;
_print(lch(u));_print(rch(u));
}
inline void print(){_print();}
#undef lch
#undef rch
}IT; int main(){
scanf("%d%d",&n,&q);
Hash.pb();Hash.pb();Hash.pb(n+);
For(i,,q){
scanf("%d%d%d",l+i,r+i,opt+i);
Hash.pb(l[i]);Hash.pb(r[i]+);
}
sort(Hash.begin(),Hash.end());
Hash.erase(unique(Hash.begin(),Hash.end()),Hash.end());
int hash_size=(int)Hash.size();
/*
For(i,1,hash_size-1) printf("%d ",Hash[i]);
puts("");
*/
IT.build(hash_size-);
// printf("%d\n",IT.query_sum(1,hash_size-1));
For(i,,q){
// IT.print();
int nl=l[i],nr=r[i];
nl=lower_bound(Hash.begin(),Hash.end(),nl)-Hash.begin();
nr=lower_bound(Hash.begin(),Hash.end(),nr+)-Hash.begin();
// printf("%d %d\n",nl,nr);
if(opt[i]^) IT.modify_set(nl,nr,);
else IT.modify_set(nl,nr,);
printf("%d\n",IT.query_sum(,hash_size-));
}
return ;
} /*
4
6
1 2 1
3 4 1
2 3 2
1 3 2
2 4 1
1 4 2 7
10
5 7 1
5 6 2
7 7 2
6 7 2
5 5 1
3 6 2
1 3 2
5 6 1
1 3 1
6 7 1 */
然后是离散化+线段树