翻卡片

发表于
字数统计: 830字 | 阅读时长 ≈ 5min

翻卡片

imgimg

做这套题的时候有一种很不优秀的做法，这里还是说一说：

把每个卡片抽象成两个点：$(A_i,B_i)$,$(B_i,A_i)$,一开始把$(A_i,B_i)$状态设置为”可用“，把$(B_i,A_i)$设置为”不可用“。那么每次操作$v$就相当于把左下角$(1,1)$、右上角$(v-1,v-1)$的矩形内的点状态取反，左下角$(1,v)$,右上角$(v,MaxV)$的矩形内的点全部把状态设置为不可用，左下角$(v,1)$,右上角$(MaxV,v)$的矩形内的点全部把状态设置为可用。画个图就明白了。
由于是二维在线的，不会写树套树只能写K-Dtree，而且还没有调对。然而结果说明这种做法比暴力好不到哪去……

题解很详细，这里直接搬过来：

j

j

代码里采用的是zkw线段树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include<stdio.h>
#include<algorithm>
#include<cstring>
#define MAXN 800005
#define MAXT 1600005
using namespace std;

char *p1,*p2,buf[1<<20];
#define GC (p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?0:*p1++)
inline int _R(){
	char s=GC;int v=0,sign=0;
	while((s!='-')&&(s>57||s<48))s=GC;
	if(s=='-')sign=1,s=GC;
	for(;s>47&&s<58;s=GC)v=v*10+s-48;
	return v;
}

struct node{
	int x,l,id,k;
}rec[MAXN];int tot;
bool operator<(node a,node b){return a.x<b.x;}

int N,K,A[MAXN],B[MAXN],V[MAXN],cnt[MAXN];
bool mark[MAXN];
int Hash[MAXN],T[MAXN];
int m,maxt[MAXT],sum[MAXT];
long long Ans;

int Find(int v){
	return lower_bound(Hash+1,Hash+Hash[0]+1,v)-Hash;
}

void build(int n){
	int i,p;
	m=1;while(m<=n)m<<=1;
	for(i=1;i<=K;i++){
		p=Find(V[i]);
		maxt[p+m]=i;
	}
	for(i=m;i;i--)maxt[i]=max(maxt[i<<1],maxt[i<<1|1]);
}

int getmax(int l,int r){
	int ret=0;
	for(l+=m-1,r+=m+1;l^r^1;l>>=1,r>>=1){
		if(~l&1)ret=max(ret,maxt[l^1]);
		if(r&1)ret=max(ret,maxt[r^1]);
	}
	return ret;
}

void _modify(int p){
	p+=m;
	while(p)sum[p]++,p>>=1;
}

int getsum(int l,int r){
	int ret=0;
	for(l+=m-1,r+=m+1;l^r^1;l>>=1,r>>=1){
		if(~l&1)ret+=sum[l^1];
		if(r&1)ret+=sum[r^1];
	}
	return ret;
}

int main(){
	int i,j,t,l,r,tmp;
	N=_R();K=_R();
	for(i=1;i<=N;i++){
		A[i]=_R();B[i]=_R();
		Hash[++Hash[0]]=min(A[i],B[i]);
		Hash[++Hash[0]]=max(A[i],B[i])-1;
	}
	for(i=1;i<=K;i++){
		V[i]=_R();
		Hash[++Hash[0]]=V[i];
	}
	
	sort(Hash+1,Hash+Hash[0]+1);
	Hash[0]=unique(Hash+1,Hash+Hash[0]+1)-(Hash+1);
	build(Hash[0]);
	
	for(i=1;i<=N;i++){
		l=min(A[i],B[i]);r=max(A[i],B[i])-1;
		if(l>r)continue;
		l=Find(l);r=Find(r);
		t=getmax(l,r);
		if(t>0)rec[++tot]=(node){t,r,i,-1},mark[i]=true;
		rec[++tot]=(node){K,r,i,1};
	}
	
	sort(rec+1,rec+tot+1);
	
	for(i=j=1;i<=tot;i++){
		while(j<=rec[i].x&&j<=K){
			_modify(Find(V[j]));
			j++;
		}
		cnt[rec[i].id]+=rec[i].k*getsum(rec[i].l,Hash[0]);
	}
	for(i=1;i<=N;i++){
		if(mark[i]){
			if(cnt[i]&1)Ans=Ans+min(A[i],B[i]);
			else Ans=Ans+max(A[i],B[i]);
		}
		else{
			if(cnt[i]&1)Ans=Ans+B[i];
			else Ans=Ans+A[i];
		}
	}
	
	printf("%lld\n",Ans);
}