一道神奇的 线段树 题目。
题目链接:QuestOJ 2135。
题目好像是来自 福建省长乐第一中学 2017.06.24。
题目
题目描述
桌面上放有 $n$ 张卡片,每张卡片都有两面,分别写着整数 $A_i$ 与 $B_i$,初始时所有卡片都是 $A_i$ 那面朝上。
接下来有 $K$ 次操作,每次操作会给出一个参数 $T_j$,这次操作会将所有朝上那面数字不超过 $T_j$ 的卡片都翻面。
现在请你求出经过所有 $K$ 次操作后,所有卡片朝上那面的数字的和。
数据范围
$$1\leq n,K\leq 2\times 10^5,1\leq A_i,B_i,T_j\leq 10^9$$
时空限制
题目 | 时间限制 | 空间限制 |
---|---|---|
QuestOJ 2135 | $$1\text{s}$$ | $$256\text{MiB}$$ |
题解
附上官方题解:
思路
这道题的正解是线段树(比赛的时候根本没有想到会是它)。
先分类讨论 $T$ 的大小对牌的正反面的情况,发现对于每一张牌可以把 $T$ 分成三类。
$$T_a < \min(A_i,B_i)\leq T_b < \max(A_i,B_i)\leq T_c$$
这三类可以分别处理:
- $T_a$
因为 $T_a < \min(A_i,B_i)$,所以无论如何第 $i$ 张牌都不会因此翻面,不需要考虑。 - $T_b$
因为 $\min(A_i,B_i)\leq T_b < \max(A_i,B_i)$,假设 $A_i>B_i$,那么假如存在一个或多个 $T_b$,都会使得第 $i$ 张牌都的上面的数字是 $\max(A_i,B_i)$。$A_i\leq B_i$ 时同理。
所以如果存在 $T_b$ 满足条件,那么这次操作后第 $i$ 张牌的大数在上面。 - $T_c$
无论如何都要翻面,所以统计在最后一个 $T_b$ 后,它的出现次数的奇偶性即可。
处理 $T_b$ 用线段树求区间最大值,统计 $T_c$ 数量用线段树(或者树状数组)数点即可。
代码
#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
reg bool f=false;
reg char ch=getchar();
reg int res=0;
while(ch<'0'||'9'<ch)f|=(ch=='-'),ch=getchar();
while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
return f?-res:res;
}
const int MAXN=200000+5;
const int MAXK=200000+5;
inline void Read(void);
inline void Work(void);
int main(void){
Read();
Work();
return 0;
}
int n,K;
int a[MAXN],b[MAXN];
int T[MAXK];
inline void Read(void){
n=read(),K=read();
for(reg int i=1;i<=n;++i)
a[i]=read(),b[i]=read();
for(reg int i=1;i<=K;++i)
T[i]=read();
return;
}
vector<int> V;
struct SegmentTree{
#define lson ( (k) << 1 )
#define rson ( (k) << 1 | 1 )
#define mid ( ( (l) + (r) ) >> 1 )
struct Node{
int Max;
};
Node unit[MAXN<<2];
inline void pushup(reg int k){
unit[k].Max=max(unit[lson].Max,unit[rson].Max);
return;
}
inline void Update(reg int k,reg int l,reg int r,reg int pos,int val){
if(l==r&&l==pos){
unit[k].Max=max(unit[k].Max,val);
return;
}
if(pos<=mid)
Update(lson,l,mid,pos,val);
if(pos>mid)
Update(rson,mid+1,r,pos,val);
pushup(k);
return;
}
inline int Query(reg int k,reg int l,reg int r,reg int L,reg int R){
if(L>R)
return 0;
if(L<=l&&r<=R){
return unit[k].Max;
}
int res=0;
if(L<=mid)
res=max(res,Query(lson,l,mid,L,R));
if(R>mid)
res=max(res,Query(rson,mid+1,r,L,R));
return res;
}
#undef lson
#undef rson
#undef mid
};
struct TreeArray{
#define lowbit(x) ( (x) & ( - (x) ) )
int m,unit[MAXN+MAXK];
inline void Init(reg int size){
m=size;
memset(unit,0,sizeof(unit));
return;
}
inline void Update(reg int ID,reg int val){
for(reg int i=ID;i<=m;i+=lowbit(i))
unit[i]+=val;
return;
}
inline int Query(reg int ID){
reg int res=0;
for(reg int i=ID;i;i-=lowbit(i))
res+=unit[i];
return res;
}
#undef lowbit
};
SegmentTree T1;
TreeArray T2;
struct Querys{
int type,id,pos,tim;
inline Querys(reg int type=0,reg int id=0,reg int pos=0,reg int tim=0):type(type),id(id),pos(pos),tim(tim){
return;
}
inline bool operator<(const Querys& a){
return tim==a.tim?type<a.type:tim>a.tim;
}
};
int last[MAXN];
int c[MAXN];
Querys Q[MAXN+MAXK];
inline int GetVal(reg int ID){
return V[ID-1];
}
inline void Work(void){
for(reg int i=1;i<=n;++i)
V.push_back(a[i]),V.push_back(b[i]);
for(reg int i=1;i<=K;++i)
V.push_back(T[i]);
sort(V.begin(),V.end());
V.erase(unique(V.begin(),V.end()),V.end());
reg int cnt=0;
for(reg int i=1;i<=K;++i){
T[i]=lower_bound(V.begin(),V.end(),T[i])-V.begin()+1;
T1.Update(1,1,V.size(),T[i],i);
Q[++cnt]=Querys(1,0,T[i],i);
}
for(reg int i=1;i<=n;++i){
a[i]=lower_bound(V.begin(),V.end(),a[i])-V.begin()+1;
b[i]=lower_bound(V.begin(),V.end(),b[i])-V.begin()+1;
reg int l=min(a[i],b[i]),r=max(a[i],b[i]);
last[i]=T1.Query(1,1,V.size(),l,r-1);
Q[++cnt]=Querys(2,i,r,last[i]);
}
T2.Init(V.size());
sort(Q+1,Q+cnt+1);
for(reg int i=1;i<=cnt;++i)
if(Q[i].type==1)
T2.Update(Q[i].pos,1);
else
c[Q[i].id]=T2.Query(V.size())-T2.Query(Q[i].pos-1);
reg ll sum=0;
for(reg int i=1;i<=n;++i){
if(a[i]==b[i])
sum+=GetVal(a[i]);
else if(a[i]<b[i]&&last[i])
if(c[i]&1)
sum+=GetVal(a[i]);
else
sum+=GetVal(b[i]);
else
if(c[i]&1)
sum+=GetVal(b[i]);
else
sum+=GetVal(a[i]);
}
printf("%lld\n",sum);
return;
}
近期评论