BZOJ3110 K大数查询

发表于 | 更新于

做法

之前学习树套树的时候，用线段树套线段树卡时限过了。 暑假的时候学CDQ分治，但不知为什么没写个整体二分的题目。就拿来练手了。 由于过于蒟蒻，看别人的代码也没有完全看懂，于是就结合对CDQ分治的理解类比写了一个。然后挂了。 然后发现是线段树写错了。每次时间戳更新之后，在修改节点的时候是在访问到之后才清空的。这样就导致了每个点都有一个子节点还存着之前的值，向上传递的时候就WA了。 然而我改对了线段树，依然WA。找到ZJOI的数据，A了。看到Discuss区里僧仙提示了一组数据，于是把各种可疑的变量都改成了long long，依然WA。WA了一晚上，我索性把CA爷的代码交了上去，居然也WA了。在网上找了好久才找到一个没有WA的，脑洞一开把这人的fread优化粘贴上，于是就A了。至今不知道怎么回事。 实现的时候为了方便，在读入数据的时候就把K大转化成K小。

CODE

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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<cassert>
//define red(x) scanf("%d",&x)
static const int S = 1310720;
 
inline int get_char() {
    static char buf[S];
    static int len = 0, pos = 0;
    if (pos == len)
        pos = 0, len = fread(buf, 1, S, stdin);
    if (pos == len) return -1;
    return buf[pos++];
}
 
template<class T> inline
void red(T& x) {
    int f = 1; x = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9')   {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    x *= f;
}

const int MAXN=50000+100;
typedef long long LL;
const LL INF=3000000000LL;

struct SegmentTree
{
	struct SegNode
	{
		int us;
		LL cnt,mrk;
	}seg[MAXN<<2];
	int TL,TR,timeline;
	SegmentTree(){timeline=0;}
	inline void Init(int x)
	{
		TL=1;
		TR=x;
	}
	inline void dispose(int pos)
	{
		if(seg[pos].us!=timeline)
		{
			seg[pos].us=timeline;
			seg[pos].cnt=0;
			seg[pos].mrk=0;
		}
	}
	void markdown(int pos,int L,int R)
	{
		dispose(pos<<1);
		dispose(pos<<1|1);
		if(seg[pos].mrk)
		{
			seg[pos<<1].mrk+=seg[pos].mrk;
			seg[pos<<1|1].mrk+=seg[pos].mrk;
			int MID=(L+R)>>1;
			seg[pos<<1].cnt+=(LL)seg[pos].mrk*(MID-L+1);
			seg[pos<<1|1].cnt+=(LL)seg[pos].mrk*(R-MID);
			seg[pos].mrk=0;	
		}
	}
	void Edit(int pos,int L,int R,int l,int r,int v)
	{
		dispose(pos);
		if(L==l && R==r)
		{
			seg[pos].mrk+=v;
			seg[pos].cnt+=(LL)(R-L+1)*v;
		}
		else
		{
			markdown(pos,L,R);
			int MID=(L+R)>>1;
			if(r<=MID)
				Edit(pos<<1,L,MID,l,r,v);
			else if(MID+1<=l)
				Edit(pos<<1|1,MID+1,R,l,r,v);
			else
				Edit(pos<<1,L,MID,l,MID,v),
				Edit(pos<<1|1,MID+1,R,MID+1,r,v);
			seg[pos].cnt=seg[pos<<1].cnt+seg[pos<<1|1].cnt;
		}
	}
	void Edit(int l,int r,int v)
	{
		Edit(1,TL,TR,l,r,v);
	}
	LL Access(int pos,int L,int R,int l,int r)
	{
		if(seg[pos].us!=timeline)
			return 0;
		if(L==l && R==r)
			return seg[pos].cnt;
		else
		{
			markdown(pos,L,R);
			int MID=(L+R)>>1;
			if(r<=MID)
				return Access(pos<<1,L,MID,l,r);
			else if(MID+1<=l)
				return Access(pos<<1|1,MID+1,R,l,r);
			else
				return Access(pos<<1,L,MID,l,MID)
					  +Access(pos<<1|1,MID+1,R,MID+1,r);
		}
	}
	inline LL Access(int l,int r)
	{
		return Access(1,TL,TR,l,r);
	}
	inline void Clear()
	{
		timeline++;
	}
}T;
struct Query
{
	int kd,l,r,id;
	LL k;
	bool operator <(const Query& x) const
	{
		return id<x.id;
	}
}p[MAXN],t[MAXN];
int ANS[MAXN];
void DC(int low,int high,int L,int R)
{
	if(L>R)
		return;
	if(low==high)
	{
		for(int i=L;i<=R;i++)
			if(p[i].kd==2)
				ANS[p[i].id]=low;
		return;
	}
	std::sort(p+L,p+R+1);
	T.Clear();
	LL mid=(low+high)>>1;
	int l=L-1,r=R+1;
	LL res;
	for(int i=L;i<=R;i++)
	{
		if(p[i].kd==1)
		{
			if(p[i].k<=mid)
			{
				T.Edit(p[i].l,p[i].r,1);
				t[++l]=p[i];
			}
			else
				t[--r]=p[i];
		}
		else
		{
			res=T.Access(p[i].l,p[i].r);
			if(p[i].k<=res)
				t[++l]=p[i];
			else
			{
				p[i].k-=res;
				t[--r]=p[i];
			}
		}
	}
	for(int i=L;i<=R;i++) p[i]=t[i];
	DC(low,mid,L,l);
	DC(mid+1,high,r,R);	
}

int main()
{
//	freopen("input.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	int n,m;red(n),red(m);
	T.Init(n);
	T.Clear();
	for(int i=1;i<=m;i++)
	{
		red(p[i].kd),red(p[i].l),red(p[i].r),red(p[i].k);
		p[i].id=i;
		ANS[i]=-MAXN;
		if(p[i].kd==1)
			T.Edit(p[i].l,p[i].r,1);
		else
			p[i].k=(LL)T.Access(p[i].l,p[i].r)-p[i].k+1;
	}
	DC(-n,n,1,m);
	for(int i=1;i<=m;i++)
		if(ANS[i]!=-MAXN)
			printf("%d\n",ANS[i]);

	return 0;
}

附上树套树 

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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#define MAXN 50100
#define MAXND MAXN*650
#define N 50000
#define S(X,NUMO) seg[X].son[NUMO]
int n,m;
int L[MAXN*10],R[MAXN*10],RT[MAXN*10];int o=0;

struct SegNode
{
	int son[2],cnt,mark;
	SegNode()
	{
		son[0]=son[1]=cnt=mark=0;
	}
}seg[MAXND];int pc=0;
inline void checks(int pos)
{
	if(!S(pos,0)) S(pos,0)=++pc;
	if(!S(pos,1)) S(pos,1)=++pc;
}
void markdown(int pos,int be,int en)
{
	if(be!=en)
	{
		checks(pos);
		if(seg[pos].mark)
		{
			int mid=(be+en)>>1;
			seg[S(pos,0)].cnt+=(mid-be+1)*seg[pos].mark;
			seg[S(pos,1)].cnt+=(en-mid)*seg[pos].mark;
			seg[S(pos,0)].mark+=seg[pos].mark;
			seg[S(pos,1)].mark+=seg[pos].mark;
			seg[pos].mark=0;
		}
	}
	else return;
}

void Build(int pos,int l,int r)
{
	L[pos]=l;R[pos]=r;
	RT[pos]=++pc;
	if(l!=r)
	{
		int mid=(l+r)>>1;
		Build(pos<<1,l,mid);
		Build(pos<<1|1,mid+1,r);
	}
}

void ins(int pos,int be,int en,int l,int r)
{
	markdown(pos,be,en);
	if(l==be && r==en)
	{
		seg[pos].cnt+=(en-be+1);
		seg[pos].mark++;
	}
	else
	{
		
		int mid=(be+en)>>1;
		if(r<=mid) ins(S(pos,0),be,mid,l,r);
		else if(mid+1<=l) ins(S(pos,1),mid+1,en,l,r);
		else
		{
			ins(S(pos,0),be,mid,l,mid);
			ins(S(pos,1),mid+1,en,mid+1,r);
		}
		seg[pos].cnt=seg[S(pos,0)].cnt+seg[S(pos,1)].cnt;
	}
}
void INS(int pos,int l,int r,int num)
{
	if(L[pos]!=R[pos])
	{
		int mid=(L[pos]+R[pos])>>1;
		if(num<=mid) INS(pos<<1,l,r,num);
		else INS(pos<<1|1,l,r,num);
	}
	ins(RT[pos],1,n,l,r);
}

int acs(int pos,int be,int en,int l,int r)
{
	//if(pos==0)
	//	return 0;
	markdown(pos,be,en);
	if(l==be && en==r)
	{
		return seg[pos].cnt;
	}
	else
	{
		int mid=(be+en)>>1;
		if(r<=mid) return acs(S(pos,0),be,mid,l,r);
		else if(l>=mid+1) return acs(S(pos,1),mid+1,en,l,r);
		else 
			return acs(S(pos,0),be,mid,l,mid)
				  +acs(S(pos,1),mid+1,en,mid+1,r);
	}
}

int ACS(int pos,int l,int r,int K)
{
	int res=acs(RT[1],1,n,l,r);

	K=res-K+1;
	res=0;
	while(L[pos]!=R[pos])
	{
		res=acs(RT[pos<<1],1,n,l,r);
		if(res<K)
		{
			K-=res;
			pos=pos<<1|1;
		}
		else pos=pos<<1;
	}	
	return L[pos];
}
int Que(int l,int r,int K)
{
	return ACS(1,l,r,K);	
} 
int main()
{
	//freopen("test.in","r",stdin);
	//freopen("test.out","w",stdout);
	scanf("%d%d",&n,&m);
	Build(1,-N,N);
	int opt,t1,t2,t3;
	for(int i=1;i<=m;i++)
	{
	//	printf("%d\n",i);
		scanf("%d%d%d%d",&opt,&t1,&t2,&t3);
		if(opt==1)//ins
			INS(1,t1,t2,t3);
		else
		{
			printf("%d\n",Que(t1,t2,t3));
		}
	}
	
	
	return 0;
}