一道神奇的 线段树 题目。

题目链接：QuestOJ 2135。

题目好像是来自 福建省长乐第一中学 2017.06.24。

[toc]

题目

题目描述

桌面上放有 $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$$

时空限制

题解

附上官方题解：

思路

这道题的正解是线段树（比赛的时候根本没有想到会是它）。

先分类讨论 $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;
}