[JOI Open 2014 day1]Fortune Telling 2(线段树+二维数点)

题目

$N$张牌，每张牌有$A$、$B$面。$A$面的值为A[i]，$B$面的值为B[i]。初始$A$面朝上。
有$K$次操作，每次操作给出一个数T[i]，把当前值小于或等于T[i]的牌翻面
求$K$次操作后，所有牌面向上的面值之和。

题解

前几天主席树学疯了…
考试的时候有这样想过，但直觉告诉我这是一道主席树的题…
感觉自己傻的不行
说明有时候换角度思考问题是很有必要的…

先考虑$A_i<B_i$的情况,$A_i>B_i$同理
若$T_j<A_i$显然这次操作不会改变第$i$号牌。
若$A_i\le T_j<B_i$这次操作会让这张牌一定变成$B_i$。
若$B_i\le T_j$这次操作会让这张牌正常的交换。
然后神仙操作来了:找到最后一次$A_i\le T_j<B_i$操作，再统计之后$B_i\le T_j$的操作，就可以直接推出这张牌的正反面。
显然是一个线段树加树状数组或者cdq分治能够做到的事情。
具体来说，就是先将$A,B,T$都离散化，然后将$T_j$插入到线段树里。维护一下下标$j$的区间最大值。
然后询问一下$[min(A_i,B_i),max(A_i,B_i)?1]$就能够找到最后一次使$A_i\le T_j<B_i$的位置$P_i$。
这样的话就是找到满足$P_i<j,max(A_i,B_i)?1<T_j$的$j$。
将它看作两个点$(P_i,max(A_i,B_i)?1)$和$(j,T_j)$。
就可以愉快的二维数点了
时间复杂度:$O(n\log n)$

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<cmath>
#include<vector>
using namespace std;
#define MAXN 200000
#define LL long long
#define INF 1000000000
#define MOD 1000000000
#define PB push_back
#define MP make_pair
#define FR first
#define SE second
#define Mid (l+r)/2
int n,k;
int A[MAXN+5],B[MAXN+5],T[MAXN+5];
int pcnt,X[MAXN*3+5],f[MAXN*3+5];
int maxx[MAXN*12+5],ans[MAXN*3+5];
struct node{
    int num,x,y;
}a[MAXN*3+5],tmp[MAXN*3+5];
bool cmp(node s1,node s2){
    return s1.x<s2.x;}
int read()
{
    int f=1,x=0;char c=getchar();while(c<'0'||c>'9'){
    if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){
    x=x*10+c-'0';c=getchar();}return x*f;
}
void Insert(int x,int l,int r,int pos,int val)
{
    if(l==r){
    maxx[x]=max(maxx[x],val);return ;}if(pos<=Mid)Insert(x<<1,l,Mid,pos,val);else Insert(x<<1|1,Mid+1,r,pos,val);maxx[x]=max(maxx[x<<1],maxx[x<<1|1]);
}
int Query(int x,int l,int r,int L,int R)
{
    if(r<L||R<l)return 0;if(L<=l&&R>=r)return maxx[x];return max(Query(x<<1,l,Mid,L,R),Query(x<<1|1,Mid+1,r,L,R));
}
void CDQ(int l,int r)
{
    if(l==r)return ;CDQ(l,Mid),CDQ(Mid+1,r);int pl=l,pr=Mid+1,p=l,cnt=0;for(int i=Mid+1;i<=r;i++)if(a[i].num==-1)cnt++;while(pl<=Mid&&pr<=r){
    if(a[pl].y<a[pr].y){
    if(a[pl].num!=-1)ans[a[pl].num]+=cnt;tmp[p++]=a[pl++];}else{
    if(a[pr].num==-1)cnt--;tmp[p++]=a[pr++];}}while(pl<=Mid){
    if(a[pl].num!=-1)ans[a[pl].num]+=cnt;tmp[p++]=a[pl++];}while(pr<=r)tmp[p++]=a[pr++];for(int i=l;i<=r;i++)a[i]=tmp[i];
}
int main()
{
    freopen("fortune.in","r",stdin);freopen("fortune.out","w",stdout);n=read(),k=read();for(int i=1;i<=n;i++)X[++pcnt]=A[i]=read(),X[++pcnt]=B[i]=read();for(int i=1;i<=k;i++)X[++pcnt]=T[i]=read();sort(X+1,X+pcnt+1);pcnt=unique(X+1,X+pcnt+1)-X-1;for(int i=1;i<=n;i++){
    A[i]=lower_bound(X+1,X+pcnt+1,A[i])-X;B[i]=lower_bound(X+1,X+pcnt+1,B[i])-X;}for(int i=1;i<=k;i++)T[i]=lower_bound(X+1,X+pcnt+1,T[i])-X;for(int i=1;i<=k;i++)Insert(1,1,pcnt,T[i],i);for(int i=1;i<=n;i++){
    f[i]=Query(1,1,pcnt,min(A[i],B[i]),max(A[i],B[i])-1);a[i]=(node){
    i,max(A[i],B[i])-1,f[i]};}for(int i=1;i<=k;i++)a[n+i]=(node){
    -1,T[i],i};sort(a+1,a+n+k+1,cmp);CDQ(1,n+k);LL res=0;for(int i=1;i<=n;i++){
    if(A[i]==B[i])res+=X[A[i]];else if(A[i]<B[i]&&f[i])res+=(ans[i]&1)?X[A[i]]:X[B[i]];else res+=(ans[i]&1)?X[B[i]]:X[A[i]];}printf("%lld",res);
}