【日常小测】浅色床单

  • 本文为博主原创，未经许可不得转载

分析：

首先我们发现题目给出的n是没有用的，于是大力离散一波暴力分就到手了

然后考虑如果本质可以相同怎么做

首先区间里的每个数都是1，考虑每进行一次操作，如果1的个数小于K，说明本次操作不在答案中，K减去1的个数，并把区间中所有的数置为0

如果1的个数大于等于K，说明K在答案中，记录一下答案，然后把区间的补集置为0

现在要求的本质不同，我们得考虑去重

如何判断两个数集是相同的呢？

我们考虑hash算法，将每个数的hash值异或起来作为数集的hash值，这样容错率比较高，为$\frac{n^2}{2^{64}}$

然后就是线段树的事情了

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
#include<bits/stdc++.h>
#define FILE "sheet"
#define MAXN 400100
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int n,m,K,cnt,tot,nowHash,L[MAXN],R[MAXN],a[MAXN],ans[MAXN],hash[MAXN],num[MAXN],tr[MAXN<<2],flag[MAXN<<2];
ull H[MAXN],Hash[MAXN];
map<ull,bool>vis;
inline int read(){
	int x=0,f=1;  char ch=getchar();
	while(ch>'9'||ch<'0')  {if(ch=='-')  f=-1;  ch=getchar();}
	while(ch>='0'&&ch<='9')  {x=x*10+ch-'0';  ch=getchar();}
	return x*f;
}
int find(int x){
	int l=1,r=tot;
	while(l+1<r){
		int mid=(l+r)>>1;
		if(hash[mid]<=x) l=mid;
		else r=mid;
	}
	return hash[l]==x?l:r;
}
void relord(int p){tr[p]=tr[p<<1]+tr[p<<1|1];}
void pushdown(int p){
	if(flag[p]){
		flag[p<<1]=1;  flag[p<<1|1]=1;
		tr[p<<1]=0;  tr[p<<1|1]=0;
		flag[p]=0;
	}
}
void build(int p,int l,int r){
	if(l==r) {tr[p]=a[l]; return;}
	int mid=(l+r)>>1;
	build(p<<1,l,mid);  build(p<<1|1,mid+1,r);
	relord(p);
}
int query(int p,int l,int r,int x,int y){
	if(x<=l&&y>=r) return tr[p];
	int mid=(l+r)>>1,ret=0;  pushdown(p);
	if(x<=mid) ret+=query(p<<1,l,mid,x,y);
	if(y>mid)  ret+=query(p<<1|1,mid+1,r,x,y);
	return ret;
}
void updata(int p,int l,int r,int x,int y){
	if(x<=l&&y>=r) {flag[p]=1; tr[p]=0;  return;}
	int mid=(l+r)>>1;  pushdown(p);
	if(x<=mid) updata(p<<1,l,mid,x,y);
	if(y>mid) updata(p<<1|1,mid+1,r,x,y);
	relord(p);
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	srand(time(0));
	n=read();  m=read();  K=read();
	for(int i=1;i<=m;++i){
		L[i]=read(); R[i]=read();
		num[++cnt]=L[i]; num[++cnt]=R[i];
		for(int j=1;j<=10;++j) H[i]=(H[i]<<15)^rand();
	}
	sort(num+1,num+cnt+1);  hash[++tot]=num[1];
	for(int i=2;i<=cnt;++i)if(num[i]!=num[i-1])hash[++tot]=num[i];
	for(int i=1;i<=m;++i) L[i]=find(L[i]),R[i]=find(R[i]);
	for(int i=1;i<=m;++i) Hash[L[i]]^=H[i],Hash[R[i]]^=H[i];
	for(int i=1;i<=tot;++i) Hash[i]^=Hash[i-1];
	for(int i=1;i<=tot;++i){
		if(vis[Hash[i]]) continue;
		vis[Hash[i]]=1,a[i]=1;
	}
	build(1,1,tot);
	for(int i=1;i<=m;++i){
		if(K<=0)  break;
		int temp=query(1,1,tot,L[i],R[i]-1);
		if(K>temp){
			updata(1,1,tot,L[i],R[i]-1);
			K-=temp;
		}
		else{
			ans[++ans[0]]=i;
			nowHash^=Hash[i];
			if(vis[nowHash]) --K;
			if(L[i]-1>0) updata(1,1,tot,1,L[i]-1);
			updata(1,1,tot,R[i],tot);
		}
	}
	printf("%d\n",ans[0]);
	for(int i=1;i<=ans[0];++i) printf("%d ",ans[i]);
	return 0;
}

本文标题:【日常小测】浅色床单

文章作者:chty

发布时间:2017年06月11日 - 21时27分

最后更新:2018年07月25日 - 21时30分

许可协议:本文为博主原创，未经许可不得转载。

文章目录
,