二分答案 – Tgotp-Blog

4552: [Tjoi2016&Heoi2016]排序

对于单独的一个数字可以用线段树搞，那么考虑二分一个数字

最后看q这个位置上数字的大小关系即可

c++代码如下：

#include<bits/stdc++.h>
#define rep(i,x,y) for(register int i = x; i <= y; ++ i)
#define repd(i,x,y) for(register int i = x; i >= y; -- i)
using namespace std;
typedef long long ll;
inline char gc()
{
	static char now[1<<16],*S,*T;
	if(S == T) { T = (S = now) + fread(now,1,1<<16,stdin);if(T == S) return EOF;}
	return *S ++;
}
template<typename T>inline void read(T&x)
{
	char c;int sign = 1;x = 0;
	do { c = gc(); if(c == '-') sign = -1; }while(!isdigit(c));
	do { x = x * 10 + c - '0'; c = gc(); }while(isdigit(c));
	x *= sign;
}

const int N = 1e5 + 50;
int a[N],l[N],r[N],op[N],sum[N<<2][2],n,m,q;
bool lzy[N << 2][3];

void build(int id,int l,int r,int x)
{
	rep(i,0,2) lzy[id][i] = 0;
	if(l == r)
	{
		sum[id][0] = a[l] < x;
		sum[id][1] = a[l] > x;
		return ;
	}
	int mid = l + r >> 1;
	build(id<<1,l,mid,x); build(id<<1|1,mid+1,r,x);
	rep(i,0,1)sum[id][i] = sum[id<<1][i] + sum[id<<1|1][i];
}

inline void put_down(int id,int l,int r)
{
	if(lzy[id][0])
	{
		lzy[id<<1][0] = (lzy[id<<1|1][0] = 1);
		lzy[id<<1][1] = (lzy[id<<1|1][1] = 0);
		lzy[id<<1][2] = (lzy[id<<1|1][2] = 0);
		sum[id<<1][0] = (sum[id<<1][1] = 0);
		sum[id<<1|1][0] = (sum[id<<1|1][1] = 0);
		lzy[id][0] = lzy[id][1] = lzy[id][2] = 0;
	}
	int mid = l + r >> 1;
	if(lzy[id][1])
	{
		lzy[id<<1][1] = (lzy[id<<1|1][1] = 1);
		lzy[id<<1][0] = (lzy[id<<1|1][0] = 0);
		lzy[id<<1][2] = (lzy[id<<1|1][2] = 0);
		sum[id<<1][1] = (sum[id<<1|1][1] = 0);
		sum[id<<1][0] = mid-l+1;sum[id<<1|1][0] = (r - (mid+1) + 1);
		lzy[id][0] = lzy[id][1] = lzy[id][2] = 0;
	}
	if(lzy[id][2])
	{
		lzy[id<<1][2] = (lzy[id<<1|1][2] = 1);
		lzy[id<<1][1] = (lzy[id<<1|1][1] = 0);
		lzy[id<<1][0] = (lzy[id<<1|1][0] = 0);
		sum[id<<1][0] = (sum[id<<1|1][0] = 0);
		sum[id<<1][1] = mid-l+1;sum[id<<1|1][1] = (r - (mid+1) + 1);
		lzy[id][0] = lzy[id][1] = lzy[id][2] = 0;
	}
}

int find(int id,int l,int r,int L,int R,int op)
{
	if(l == L && r == R) return sum[id][op];
	int mid = l + r >> 1;
	put_down(id,l,r);
	if(R <= mid) return find(id<<1,l,mid,L,R,op);
	else if(L > mid) return find(id<<1|1,mid+1,r,L,R,op);
	else return find(id<<1,l,mid,L,mid,op) + find(id<<1|1,mid+1,r,mid+1,R,op);
}

void clear(int id,int l,int r,int L,int R)
{
	if(l == L && r == R)
	{
		lzy[id][0] = 1; lzy[id][1] = 0; lzy[id][2] = 0;
		sum[id][0] = (sum[id][1] = 0);
		return;
	}
	put_down(id,l,r);
	int mid = l + r >> 1;
	if(L > mid) clear(id<<1|1,mid+1,r,L,R);
	else if(R <= mid) clear(id<<1,l,mid,L,R);
	else clear(id<<1,l,mid,L,mid),clear(id<<1|1,mid+1,r,mid+1,R);
	rep(i,0,1)sum[id][i] = sum[id<<1][i] + sum[id<<1|1][i];
}

void Fill(int id,int l,int r,int L,int R,int op)
{
	if(l == L && r == R)
	{
		lzy[id][op] = 1;
		lzy[id][0] = (lzy[id][op==1?2:1] = 0);
		sum[id][op-1] = r - l + 1;
		sum[id][(op-1)^1] = 0;
		return;
	}
	put_down(id,l,r);
	int mid = l + r >> 1;
	if(L > mid) Fill(id<<1|1,mid+1,r,L,R,op);
	else if(R <= mid) Fill(id<<1,l,mid,L,R,op);
	else Fill(id<<1,l,mid,L,mid,op),Fill(id<<1|1,mid+1,r,mid+1,R,op);
	rep(i,0,1)sum[id][i] = sum[id<<1][i] + sum[id<<1|1][i];
}

inline int check(int x)
{
	build(1,1,n,x);
	
	rep(i,1,m)
	{
		int p1 = find(1,1,n,l[i],r[i],0);
		int p2 = find(1,1,n,l[i],r[i],1);
		clear(1,1,n,l[i],r[i]);
		if(p1)
		{
			if(op[i] == 0)
				Fill(1,1,n,l[i],l[i] + p1 - 1,1);	
			else
				Fill(1,1,n,r[i] - p1 + 1,r[i],1);
		}
		if(p2)
		{
			if(op[i] == 0)
				Fill(1,1,n,r[i] - p2 + 1,r[i],2);
			else 
				Fill(1,1,n,l[i],l[i] + p2 - 1,2);
		}
	}
	int t1 = find(1,1,n,q,q,0);
	int t2 = find(1,1,n,q,q,1);
	if(!t1 && !t2) return 1;
	if(t2) return 2;
	if(t1) return 3;
}

int main()
{
	read(n); read(m); 
	rep(i,1,n) read(a[i]);
	rep(i,1,m) read(op[i]),read(l[i]),read(r[i]);
	read(q);
	int l = 1,r = n,mid,ans;
	while(l <= r)
	{
		int t = check(mid=l+r>>1);
		if(t == 1) { ans = mid; break; }
		if(t == 2) l = mid + 1;
		if(t == 3) r = mid - 1;
	}

	cout << ans << endl;
	//cout << fixed << setprecision(3)<< (clock()/(double)CLOCKS_PER_SEC);
	return 0;
}

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

#include<bits/stdc++.h>

#define rep(i,x,y) for(register int i = x; i <= y; ++ i)

#define repd(i,x,y) for(register int i = x; i >= y; -- i)

using namespace std;

typedef long long ll;

inline char gc()

{

static char now[1<<16],*S,*T;

if(S == T) { T = (S = now) + fread(now,1,1<<16,stdin);if(T == S) return EOF;}

return *S ++;

}

template<typename T>inline void read(T&x)

{

char c;int sign = 1;x = 0;

do { c = gc(); if(c == '-') sign = -1; }while(!isdigit(c));

do { x = x * 10 + c - '0'; c = gc(); }while(isdigit(c));

x *= sign;

}

const int N = 1e5 + 50;

int a[N],l[N],r[N],op[N],sum[N<<2][2],n,m,q;

bool lzy[N << 2][3];

void build(int id,int l,int r,int x)

{

rep(i,0,2) lzy[id][i] = 0;

if(l == r)

{

sum[id][0] = a[l] < x;

sum[id][1] = a[l] > x;

return ;

}

int mid = l + r >> 1;

build(id<<1,l,mid,x); build(id<<1|1,mid+1,r,x);

rep(i,0,1)sum[id][i] = sum[id<<1][i] + sum[id<<1|1][i];

}

inline void put_down(int id,int l,int r)

{

if(lzy[id][0])

{

lzy[id<<1][0] = (lzy[id<<1|1][0] = 1);

lzy[id<<1][1] = (lzy[id<<1|1][1] = 0);

lzy[id<<1][2] = (lzy[id<<1|1][2] = 0);

sum[id<<1][0] = (sum[id<<1][1] = 0);

sum[id<<1|1][0] = (sum[id<<1|1][1] = 0);

lzy[id][0] = lzy[id][1] = lzy[id][2] = 0;

}

int mid = l + r >> 1;

if(lzy[id][1])

{

lzy[id<<1][1] = (lzy[id<<1|1][1] = 1);

lzy[id<<1][0] = (lzy[id<<1|1][0] = 0);

lzy[id<<1][2] = (lzy[id<<1|1][2] = 0);

sum[id<<1][1] = (sum[id<<1|1][1] = 0);

sum[id<<1][0] = mid-l+1;sum[id<<1|1][0] = (r - (mid+1) + 1);

lzy[id][0] = lzy[id][1] = lzy[id][2] = 0;

}

if(lzy[id][2])

{

lzy[id<<1][2] = (lzy[id<<1|1][2] = 1);

lzy[id<<1][1] = (lzy[id<<1|1][1] = 0);

lzy[id<<1][0] = (lzy[id<<1|1][0] = 0);

sum[id<<1][0] = (sum[id<<1|1][0] = 0);

sum[id<<1][1] = mid-l+1;sum[id<<1|1][1] = (r - (mid+1) + 1);

lzy[id][0] = lzy[id][1] = lzy[id][2] = 0;

}

int find(int id,int l,int r,int L,int R,int op)

{

if(l == L && r == R) return sum[id][op];

int mid = l + r >> 1;

put_down(id,l,r);

if(R <= mid) return find(id<<1,l,mid,L,R,op);

else if(L > mid) return find(id<<1|1,mid+1,r,L,R,op);

else return find(id<<1,l,mid,L,mid,op) + find(id<<1|1,mid+1,r,mid+1,R,op);

}

void clear(int id,int l,int r,int L,int R)

{

if(l == L && r == R)

{

lzy[id][0] = 1; lzy[id][1] = 0; lzy[id][2] = 0;

sum[id][0] = (sum[id][1] = 0);

return;

}

put_down(id,l,r);

int mid = l + r >> 1;

if(L > mid) clear(id<<1|1,mid+1,r,L,R);

else if(R <= mid) clear(id<<1,l,mid,L,R);

else clear(id<<1,l,mid,L,mid),clear(id<<1|1,mid+1,r,mid+1,R);

rep(i,0,1)sum[id][i] = sum[id<<1][i] + sum[id<<1|1][i];

}

void Fill(int id,int l,int r,int L,int R,int op)

{

if(l == L && r == R)

{

lzy[id][op] = 1;

lzy[id][0] = (lzy[id][op==1?2:1] = 0);

sum[id][op-1] = r - l + 1;

sum[id][(op-1)^1] = 0;

return;

}

put_down(id,l,r);

int mid = l + r >> 1;

if(L > mid) Fill(id<<1|1,mid+1,r,L,R,op);

else if(R <= mid) Fill(id<<1,l,mid,L,R,op);

else Fill(id<<1,l,mid,L,mid,op),Fill(id<<1|1,mid+1,r,mid+1,R,op);

rep(i,0,1)sum[id][i] = sum[id<<1][i] + sum[id<<1|1][i];

}

inline int check(int x)

{

build(1,1,n,x);

rep(i,1,m)

{

int p1 = find(1,1,n,l[i],r[i],0);

int p2 = find(1,1,n,l[i],r[i],1);

clear(1,1,n,l[i],r[i]);

if(p1)

{

if(op[i] == 0)

Fill(1,1,n,l[i],l[i] + p1 - 1,1);

else

Fill(1,1,n,r[i] - p1 + 1,r[i],1);

}

if(p2)

{

if(op[i] == 0)

Fill(1,1,n,r[i] - p2 + 1,r[i],2);

else

Fill(1,1,n,l[i],l[i] + p2 - 1,2);

}

int t1 = find(1,1,n,q,q,0);

int t2 = find(1,1,n,q,q,1);

if(!t1 && !t2) return 1;

if(t2) return 2;

if(t1) return 3;

}

int main()

{

read(n); read(m);

rep(i,1,n) read(a[i]);

rep(i,1,m) read(op[i]),read(l[i]),read(r[i]);

read(q);

int l = 1,r = n,mid,ans;

while(l <= r)

{

int t = check(mid=l+r>>1);

if(t == 1) { ans = mid; break; }

if(t == 2) l = mid + 1;

if(t == 3) r = mid - 1;

}

cout << ans << endl;

//cout << fixed << setprecision(3)<< (clock()/(double)CLOCKS_PER_SEC);

return 0;

}

2018年9月4日 448 0 /

BZOJ

Tag: 二分答案线段树

Life Forms

思路不难想，求出sa以后二分随便搞搞，和上一题比较像。细节卡死人。。。

注意是大于一半。。。一开始以为是至少一半疯狂wa。。。

然后现在还把用来对拍的程序卡掉了。。。

c++代码如下：

/* code by Tgotp
    poj 3294  */
#include<algorithm>
#include<cstdio>
#include<cstring>
#define rep(i,x,y) for(register int i = x ;i <= y; ++ i)
#define repd(i,x,y) for(register int i = x ; i >= y; -- i)
using namespace std;

const int N = 1e5 + 500;
char s[1011],S[N];
int len,x[N],y[N << 1],sa[N],buc[N],height[N],rank[N];
int n,pos[111],belong[N];

inline void clear()
{
	rep(i,0,len - 1) S[i] = 0;
	memset(buc,0,sizeof buc);
	memset(x,0,sizeof x);
	len = 0;
}

inline void swap(int&x,int&y) { int t = x; x = y; y = t; }

inline void SA()
{
	int m = 455;
	rep(i,0,len - 1) ++buc[x[i]];
	rep(i,1,m) buc[i] += buc[i - 1];
	repd(i,len - 1,0) sa[--buc[x[i]]] = i;
	for(register int k = 1 ;k <= len; k <<= 1)
	{
		int p = 0;
		repd(i,len - 1,len - k) y[p++] = i;
		rep(i,0,len - 1) if(sa[i] >= k) y[p++] = sa[i] - k;
		
		rep(i,0,m) buc[i] = 0;
		rep(i,0,len - 1) ++buc[x[i]];
		rep(i,1,m) buc[i] += buc[i - 1];
		repd(i,len - 1,0) sa[--buc[x[y[i]]]] = y[i];
		
		rep(i,0,len - 1) swap(x[i],y[i]);
		p = 1; x[sa[0]] = 0;
		rep(i,1,len - 1)
			if(y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k])
				x[sa[i]] = p - 1;
			else x[sa[i]] = p++;
		
		if(p == len) break;
		m = p;
	}
	
	int p = 0;
	rep(i,0,len - 1) rank[sa[i]] = i;
	rep(i,0,len - 1)
	{
		if(p) --p;
		if(rank[i] == 0) continue;
		int t = sa[rank[i] - 1];
		while(t + p < len && i + p < len && S[t + p] == S[i + p] ) ++p;
		height[rank[i]] = p;
	}
}

inline bool check(int x)
{
	rep(i,1,len - 1)
	{
		int l,r;
		l = i; while(height[l] < x && l < len) ++l;
		r = l; while(height[r] >= x && r < len) ++r;
		
		if(l == len) break;
		
		rep(k,1,n) pos[k] = -1;
		rep(k,l - 1,r - 1)
			pos[belong[sa[k]]] = sa[k];
		
		int num = 0;
		rep(k,1,n) if(~pos[k]) ++num;
		if(num > n / 2) return true;
		
		i = r;
	}
	return false;
}

inline void solve()
{
	clear();
	
	rep(i,1,n)
	{
		scanf("%s",s);
		int Len = strlen(s);
		rep(j,0,Len - 1) x[j + len] = s[j] + 100,S[j + len] = s[j],belong[j + len] = i;
		x[len + Len] = i;S[len + Len] = i;
		belong[len + Len] = 0;
		len += Len + 1;
	}
	
	SA();
	
	int l = 0,r = len - 1,mid,ans;
	
	while(l <= r )
	{
		if(check(mid = l + r >> 1)) l = mid + 1,ans = mid;
		else r = mid - 1;
	}
	
	if(ans == 0) puts("?");
	else 
	{
		rep(i,1,len - 1)
		{
			int l,r;
			l = i; while(height[l] < ans && l < len) ++l;
			r = l; while(height[r] >= ans && r < len) ++r;
			
			if(l == len) break;
			
			rep(k,1,n) pos[k] = -1;
			rep(k,l - 1,r - 1)
				pos[belong[sa[k]]] = sa[k];
			
			int num = 0;
			rep(k,1,n) if(~pos[k]) ++num;
			if(num > n / 2) 
			{
				rep(k,0,ans - 1) printf("%c",S[sa[l - 1] + k]);
				puts("");
			}
			
			i = r;
		}
	}
	puts("");
}

int main()
{
//	freopen("1.in","r",stdin);
//	freopen("my.out","w",stdout);
	while(scanf("%d",&n),n != 0) solve();
	return 0;
}

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

/* code by Tgotp

poj 3294 */

#include<algorithm>

#include<cstdio>

#include<cstring>

#define rep(i,x,y) for(register int i = x ;i <= y; ++ i)

#define repd(i,x,y) for(register int i = x ; i >= y; -- i)

using namespace std;

const int N = 1e5 + 500;

char s[1011],S[N];

int len,x[N],y[N << 1],sa[N],buc[N],height[N],rank[N];

int n,pos[111],belong[N];

inline void clear()

{

rep(i,0,len - 1) S[i] = 0;

memset(buc,0,sizeof buc);

memset(x,0,sizeof x);

len = 0;

}

inline void swap(int&x,int&y) { int t = x; x = y; y = t; }

inline void SA()

{

int m = 455;

rep(i,0,len - 1) ++buc[x[i]];

rep(i,1,m) buc[i] += buc[i - 1];

repd(i,len - 1,0) sa[--buc[x[i]]] = i;

for(register int k = 1 ;k <= len; k <<= 1)

{

int p = 0;

repd(i,len - 1,len - k) y[p++] = i;

rep(i,0,len - 1) if(sa[i] >= k) y[p++] = sa[i] - k;

rep(i,0,m) buc[i] = 0;

rep(i,0,len - 1) ++buc[x[i]];

rep(i,1,m) buc[i] += buc[i - 1];

repd(i,len - 1,0) sa[--buc[x[y[i]]]] = y[i];

rep(i,0,len - 1) swap(x[i],y[i]);

p = 1; x[sa[0]] = 0;

rep(i,1,len - 1)

if(y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k])

x[sa[i]] = p - 1;

else x[sa[i]] = p++;

if(p == len) break;

m = p;

}

int p = 0;

rep(i,0,len - 1) rank[sa[i]] = i;

rep(i,0,len - 1)

{

if(p) --p;

if(rank[i] == 0) continue;

int t = sa[rank[i] - 1];

while(t + p < len && i + p < len && S[t + p] == S[i + p] ) ++p;

height[rank[i]] = p;

}

inline bool check(int x)

{

rep(i,1,len - 1)

{

int l,r;

l = i; while(height[l] < x && l < len) ++l;

r = l; while(height[r] >= x && r < len) ++r;

if(l == len) break;

rep(k,1,n) pos[k] = -1;

rep(k,l - 1,r - 1)

pos[belong[sa[k]]] = sa[k];

int num = 0;

rep(k,1,n) if(~pos[k]) ++num;

if(num > n / 2) return true;

i = r;

}

return false;

}

inline void solve()

{

clear();

rep(i,1,n)

{

scanf("%s",s);

int Len = strlen(s);

rep(j,0,Len - 1) x[j + len] = s[j] + 100,S[j + len] = s[j],belong[j + len] = i;

x[len + Len] = i;S[len + Len] = i;

belong[len + Len] = 0;

len += Len + 1;

}

SA();

int l = 0,r = len - 1,mid,ans;

while(l <= r )

{

if(check(mid = l + r >> 1)) l = mid + 1,ans = mid;

else r = mid - 1;

}

if(ans == 0) puts("?");

else

{

rep(i,1,len - 1)

{

int l,r;

l = i; while(height[l] < ans && l < len) ++l;

r = l; while(height[r] >= ans && r < len) ++r;

if(l == len) break;

rep(k,1,n) pos[k] = -1;

rep(k,l - 1,r - 1)

pos[belong[sa[k]]] = sa[k];

int num = 0;

rep(k,1,n) if(~pos[k]) ++num;

if(num > n / 2)

{

rep(k,0,ans - 1) printf("%c",S[sa[l - 1] + k]);

puts("");

}

i = r;

}

puts("");

}

int main()

{

// freopen("1.in","r",stdin);

// freopen("my.out","w",stdout);

while(scanf("%d",&n),n != 0) solve();

return 0;

}

数据生成代码：
[cra[......]

2017年12月22日 669 0 /

poj

Tag: sa 二分答案

PHRASES - Relevant Phrases of Annihilation

有点难度的sa，把所有的字符串串在一起，然后分段保证段上有长为x的两个子串

首先求出sa，然后再求出height 数组，然后二分答案，对于每段就枚举height差值不超过二分值得段。

然后记录在每一段出现最早与最晚得值（判断有无两个串），然后判断。

搞定。

c++代码如下：[......]

2017年12月21日 772 0 /

SPOJ

Tag: sa 二分答案

P3939 数颜色

因为交换只会交换相邻两数，所以交换很好写。

用vector存一下每个颜色出现的位置，然后对于查找的颜色在vector上二分。

c++代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<stack>
#include<vector>
#include<algorithm>
#define repd(i,x,y) for(register int i = x ;i >= y; --i)
#define rep(i,x,y) for(register int i = x ;i <= y;++i)
using namespace std;
typedef long long ll;
template<typename T>inline void read(T&x)
{
    x = 0;char c;int sign = 1;
    do { c = getchar(); if(c == '-') sign = -1; }while(c < '0' || c > '9');
    do { x = x * 10 + c - '0'; c = getchar(); }while(c <= '9' && c >= '0');
    x *= sign;
}

const int N = 3e5 + 500;
int n,m,a[N],id[N];
vector<int>color[N];

int main()
{
	read(n);read(m);
	
	rep(i,1,3e5)color[i].push_back(0);
	rep(i,1,n)
	{
		read(a[i]);
		color[a[i]].push_back(i);
		id[i] = color[a[i]].size() - 1;
	}
	rep(i,1,3e5)color[i].push_back(n + 1);
	
	int op,l,r,x;
	rep(i,1,m)
	{
		read(op);
		if(op == 1)
		{
			read(l);read(r);read(x);
			int L = 0,R = ((int)color[x].size()) - 1,mid,z1 = 0,z2 = -1;
			while(L <= R)
			{
				if(color[x][mid = (L + R) >> 1] < l) z1 = mid,L = mid + 1;
				else R = mid - 1;
			}
			L = 0,R = ((int)color[x].size()) - 1;
			while(L <= R)
			{
				if(color[x][mid = (L + R) >> 1] > r) z2 = mid,R = mid - 1;
				else L = mid + 1;
			}
			printf("%d\n",z2 - z1 - 1 > 0 ? z2 - z1 - 1 : 0 );
		}
		else 
		{
			read(x);
			if(a[x] == a[x + 1]) continue;
			color[ a[ x ] ][ id[ x ] ]++;
			color[a[x + 1]][id[x + 1]]--;
			swap(a[x],a[x+1]);swap(id[x],id[x + 1]);
		}
	}
	return 0;
}

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<queue>

#include<stack>

#include<vector>

#include<algorithm>

#define repd(i,x,y) for(register int i = x ;i >= y; --i)

#define rep(i,x,y) for(register int i = x ;i <= y;++i)

using namespace std;

typedef long long ll;

template<typename T>inline void read(T&x)

{

x = 0;char c;int sign = 1;

do { c = getchar(); if(c == '-') sign = -1; }while(c < '0' || c > '9');

do { x = x * 10 + c - '0'; c = getchar(); }while(c <= '9' && c >= '0');

x *= sign;

}

const int N = 3e5 + 500;

int n,m,a[N],id[N];

vector<int>color[N];

int main()

{

read(n);read(m);

rep(i,1,3e5)color[i].push_back(0);

rep(i,1,n)

{

read(a[i]);

color[a[i]].push_back(i);

id[i] = color[a[i]].size() - 1;

}

rep(i,1,3e5)color[i].push_back(n + 1);

int op,l,r,x;

rep(i,1,m)

{

read(op);

if(op == 1)

{

read(l);read(r);read(x);

int L = 0,R = ((int)color[x].size()) - 1,mid,z1 = 0,z2 = -1;

while(L <= R)

{

if(color[x][mid = (L + R) >> 1] < l) z1 = mid,L = mid + 1;

else R = mid - 1;

}

L = 0,R = ((int)color[x].size()) - 1;

while(L <= R)

{

if(color[x][mid = (L + R) >> 1] > r) z2 = mid,R = mid - 1;

else L = mid + 1;

}

printf("%d\n",z2 - z1 - 1 > 0 ? z2 - z1 - 1 : 0 );

}

else

{

read(x);

if(a[x] == a[x + 1]) continue;

color[ a[ x ] ][ id[ x ] ]++;

color[a[x + 1]][id[x + 1]]--;

swap(a[x],a[x+1]);swap(id[x],id[x + 1]);

}

return 0;

}

2017年11月2日 1,000 0 /

Luogu

Tag: 二分答案

3110: [Zjoi2013]K大数查询

整体二分，用线段树维护区间大于mid 的值

c++代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define rep(i,x,y) for(register int i = x ;i <= (y);++i)
#define repd(i,x,y) for(register int i = x ;i >= (y); -- i)
#define abs(x) (x > 0 ? x : -(x))
using namespace std;
typedef long long ll;
template<class T> inline void chkmin(T&a,T b) { return a > b ? a = b,1 : 0; }
template<class T> inline void chkmax(T&a,T b) { return a < b ? a = b,1 : 0; }
template<typename T>inline void read(T&x){
    x = 0;char c;int sign = 1;
    do { c = getchar(); if(c == '-') sign = -1; }while(c < '0' || c > '9');
    do { x = x * 10 + c - '0'; c = getchar(); }while(c <= '9' &&  c >= '0');
    x *= sign;
}

const int M = 5e4 + 50;

int ans[M],n,m;
struct QUE
{
    int l,r,id,op,v;
    bool k;
}q[M];

struct Segment_tree
{
    int ql,qr;
	ll add[M<<2],sum[M<<2];
    bool clr[M<<2];
    
    #define lc id<<1
    #define rc id<<1|1
    inline void init() { sum[1] = add[1] = 0;clr[1] = 1; }
    inline void update(int id) { sum[id] = sum[lc] + sum[rc]; }
    inline void putdown(int id,int l,int r)
    {
        if(clr[id])
        {
            sum[lc] = sum[rc] = add[lc] = add[rc] = 0;
            clr[lc] = clr[rc] = 1;clr[id] = 0;
        }
        int mid = (l + r) >> 1;
        if(add[id])
        {
            add[lc] += add[id]; add[rc] += add[id];
            sum[lc] += (mid - l + 1)*add[id];sum[rc] += (r - mid)*add[id];
            add[id] = 0;
        }
    }
    void Add(int id,int l,int r)
    {
        if(ql <= l && qr >= r) { add[id]++,sum[id] += r - l + 1 ; return; }
        int mid = (l + r) >> 1;
		putdown(id,l,r);
        if(ql <= mid) Add(lc,l,mid); if(qr > mid) Add(rc,mid + 1,r);
        update(id);
    }
    ll query(int id,int l,int r)
    {
        if(ql <= l && qr >= r)  return sum[id];
        ll res = 0;int mid = (l + r) >> 1;
		putdown(id,l,r);
        if(ql <= mid) res += query(lc,l,mid); if(qr > mid) res += query(rc,mid + 1,r);
        return res;
    }
}seg;

inline bool cmp(QUE a,QUE b){ return a.k == b.k ? a.id < b.id : a.k < b.k; }

void solve(int L,int R,int l,int r)
{
    if(l > r) return;
    if(L == R) {
        rep(i,l,r) if(q[i].op == 2) ans[q[i].id] = L;
        return ;
    }
    seg.init();
    int mid = (L + R ) >> 1,t = l - 1;
	ll s;
    rep(i,l,r)
    {
        if(q[i].op == 1){
            if(q[i].v > mid){
                seg.ql = q[i].l;seg.qr = q[i].r;
                seg.Add(1,1,n); q[i].k = 1;
            }else t++,q[i].k = 0;
        }
        else 
        {
            seg.ql = q[i].l;seg.qr = q[i].r;
            s = seg.query(1,1,n);
            if(q[i].v <= s ) q[i].k = 1 ;
            else t++,q[i].k = 0,q[i].v -= s;
        }
    }
    sort(q + l, q + r + 1,cmp);
    solve(L,mid,l,t) ; solve(mid + 1,R,t + 1,r);
}

int main()
{
    memset(ans,-1,sizeof ans );
    read(n);read(m);
    rep(i,1,m) {
        read(q[i].op) ; read(q[i].l);read(q[i].r);read(q[i].v);
        q[i].id = i;
    }
    solve(1,n,1,m);
    rep(i,1,m) if(ans[i] != -1)
            printf("%d\n",ans[i]);
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define rep(i,x,y) for(register int i = x ;i <= (y);++i)

#define repd(i,x,y) for(register int i = x ;i >= (y); -- i)

#define abs(x) (x > 0 ? x : -(x))

using namespace std;

typedef long long ll;

template<class T> inline void chkmin(T&a,T b) { return a > b ? a = b,1 : 0; }

template<class T> inline void chkmax(T&a,T b) { return a < b ? a = b,1 : 0; }

template<typename T>inline void read(T&x){

x = 0;char c;int sign = 1;

do { c = getchar(); if(c == '-') sign = -1; }while(c < '0' || c > '9');

do { x = x * 10 + c - '0'; c = getchar(); }while(c <= '9' && c >= '0');

x *= sign;

}

const int M = 5e4 + 50;

int ans[M],n,m;

struct QUE

{

int l,r,id,op,v;

bool k;

}q[M];

struct Segment_tree

{

int ql,qr;

ll add[M<<2],sum[M<<2];

bool clr[M<<2];

#define lc id<<1

#define rc id<<1|1

inline void init() { sum[1] = add[1] = 0;clr[1] = 1; }

inline void update(int id) { sum[id] = sum[lc] + sum[rc]; }

inline void putdown(int id,int l,int r)

{

if(clr[id])

{

sum[lc] = sum[rc] = add[lc] = add[rc] = 0;

clr[lc] = clr[rc] = 1;clr[id] = 0;

}

int mid = (l + r) >> 1;

if(add[id])

{

add[lc] += add[id]; add[rc] += add[id];

sum[lc] += (mid - l + 1)*add[id];sum[rc] += (r - mid)*add[id];

add[id] = 0;

}

void Add(int id,int l,int r)

{

if(ql <= l && qr >= r) { add[id]++,sum[id] += r - l + 1 ; return; }

int mid = (l + r) >> 1;

putdown(id,l,r);

if(ql <= mid) Add(lc,l,mid); if(qr > mid) Add(rc,mid + 1,r);

update(id);

}

ll query(int id,int l,int r)

{

if(ql <= l && qr >= r) return sum[id];

ll res = 0;int mid = (l + r) >> 1;

putdown(id,l,r);

if(ql <= mid) res += query(lc,l,mid); if(qr > mid) res += query(rc,mid + 1,r);

return res;

}

}seg;

inline bool cmp(QUE a,QUE b){ return a.k == b.k ? a.id < b.id : a.k < b.k; }

void solve(int L,int R,int l,int r)

{

if(l > r) return;

if(L == R) {

rep(i,l,r) if(q[i].op == 2) ans[q[i].id] = L;

return ;

}

seg.init();

int mid = (L + R ) >> 1,t = l - 1;

ll s;

rep(i,l,r)

{

if(q[i].op == 1){

if(q[i].v > mid){

seg.ql = q[i].l;seg.qr = q[i].r;

seg.Add(1,1,n); q[i].k = 1;

}else t++,q[i].k = 0;

}

else

{

seg.ql = q[i].l;seg.qr = q[i].r;

s = seg.query(1,1,n);

if(q[i].v <= s ) q[i].k = 1 ;

else t++,q[i].k = 0,q[i].v -= s;

}

sort(q + l, q + r + 1,cmp);

solve(L,mid,l,t) ; solve(mid + 1,R,t + 1,r);

}

int main()

{

memset(ans,-1,sizeof ans );

read(n);read(m);

rep(i,1,m) {

read(q[i].op) ; read(q[i].l);read(q[i].r);read(q[i].v);

q[i].id = i;

}

solve(1,n,1,m);

rep(i,1,m) if(ans[i] != -1)

printf("%d\n",ans[i]);

return 0;

}

2017年10月12日 710 0 /

BZOJ

Tag: 二分答案整体二分线段树

P2538 [SCOI2008]城堡

爆搜 + 贪心 + 二分 + floyd；

记住：大胆假设，不用证明

先存图，观察数据范围n <= 50 ，直接用floyd求出最短路。

继续二分最大长度 c ，对于每个已有城堡的城市，直接去标记其能到达的城市，然后对于不能到达的，

我们将其距离不超过枚举的c的点期望[......]

2017年9月27日 1,449 0 /

Luogu

Tag: floyd 二分答案期望

1014: [JSOI2008]火星人prefix

一脸萎靡。。。

这题做的疯。

数据真心有毒。

数字和字母之前不等距 exm？

二分 + hash + splay

我只能说是个p的神题。

bz的常数卡的我疯狂。。。

就是一般的splay入门题，看看代码就好了。

c++代码如下：
[crayon-5c[......]

2017年9月22日 989 0 /

BZOJ

Tag: hash Splay 二分答案

P1024 一元三次方程求解

回归刷水题，二分的水题，直接见代码，可以当成二分答案的入门题了。

c++代码如下：

#include<iostream>
#include<cstdio>
#define rep(i,x,y) for(register int i = x;i <= y;++i)
using namespace std;
double a,b,c,d;
inline double f(double x){ return a*x*x*x+b*x*x+c*x+d; }
int main()
{
	scanf("%lf%lf%lf%lf",&a,&b,&c,&d);
	rep(i,-100,100)
	{
		double l = i,r = i + 1,mid;
		if(f(l) == 0) { printf("%.2lf ",l); continue; }
		if(f(l) * f(r) < 0)
		{
			while(r - l > 0.00001)
			{
				if(f(l) * f(mid = (l+r)/2) < 0) r = mid;
				else l = mid;
			}
			printf("%.2lf ",l);
		}
	}
	return 0;
}

#include<iostream>

#include<cstdio>

#define rep(i,x,y) for(register int i = x;i <= y;++i)

using namespace std;

double a,b,c,d;

inline double f(double x){ return a*x*x*x+b*x*x+c*x+d; }

int main()

{

scanf("%lf%lf%lf%lf",&a,&b,&c,&d);

rep(i,-100,100)

{

double l = i,r = i + 1,mid;

if(f(l) == 0) { printf("%.2lf ",l); continue; }

if(f(l) * f(r) < 0)

{

while(r - l > 0.00001)

{

if(f(l) * f(mid = (l+r)/2) < 0) r = mid;

else l = mid;

}

printf("%.2lf ",l);

}

return 0;

}

2017年8月27日 1,418 0 /

Luogu

Tag: 二分答案

BZOJ1067: [SCOI2007]降雨量

时隔半个月写的第一题，还是改的原来的。。。

这道题算法很显而易见，重点在于细节处理。

建代码的处理咯

c++代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#define rep(i,x,y) for(register int i = x;i <= y;++i)
using namespace std;
inline void read(int&x)
{
	x = 0; char c;int sign = 1;
	do { c = getchar();if(c == '-') sign = -1; }while(c < '0' || c > '9');
	do { x = x*10 + c - '0';c = getchar(); }while(c <= '9' && c >= '0');
	x *= sign;
}

const int N = 5e4 + 50;
int n,m,x,id[N],val[N];

struct node
{
	int left,right,val;
}tree[N*4];

void build(int id,int l,int r)
{
	tree[id].left = l;tree[id].right = r;
	if(l == r)  { tree[id].val = val[l]; return ; }
	int mid = (l + r) >>1;
	build(id<<1,l,mid);build(id<<1|1,mid+1,r);
	tree[id].val = max(tree[id<<1].val,tree[id<<1|1].val);
}

int query(int id,int l,int r)
{
	if(l == tree[id].left && tree[id].right == r) return tree[id].val;
	int mid = (tree[id].left + tree[id].right) >>1;
	if(l > mid) return query(id<<1|1,l,r);
	if(r <= mid) return query(id<<1,l,r);
	return max(query(id<<1,l,mid),query(id<<1|1,mid+1,r));
}
inline int find(int x)
{
	int l = 1,r = n,mid,num;
	while(l <= r)
	{
		if(id[mid = (l+r)>>1] == x) return mid;
		else if(id[mid] < x) l = mid + 1;
		else r = mid - 1;
	}
	return l;
}
int main()
{
	read(n);
	int x,y;
	rep(i,1,n)
	{
		read(x);read(y);
		id[i] = x;val[i] = y;
	}
	build(1,1,n);
	read(m);
	while(m--)
	{
		bool e = 0; 
		read(y); read(x);
		if(y > x) { puts("false");continue; } 
		if(x == y) { puts("true");continue; } 
		int Y = find(y), X = find(x);int Z = Y;
		if(id[X] != x){ 
			if(Y + 1 <= X - 1 && id[Y] == y) puts(query(1,Y+1,X-1) >= val[Y] ? "false":"maybe");
			else puts("maybe");
			continue; 
		}
		if(y == id[Y]){
			if(val[Y] < val[X]) { puts("false");continue; }
			++Y;
		}else e = 1;
		if(X == Y){ puts(x - y == X - Z ?"true":"maybe"); continue; }
		int ans = query(1,Y,X-1);
		puts(val[X] <= ans?"false":x - y == X - Z && !e ?"true":"maybe");
	}
	return 0;
}

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

#include<algorithm>

#define rep(i,x,y) for(register int i = x;i <= y;++i)

using namespace std;

inline void read(int&x)

{

x = 0; char c;int sign = 1;

do { c = getchar();if(c == '-') sign = -1; }while(c < '0' || c > '9');

do { x = x*10 + c - '0';c = getchar(); }while(c <= '9' && c >= '0');

x *= sign;

}

const int N = 5e4 + 50;

int n,m,x,id[N],val[N];

struct node

{

int left,right,val;

}tree[N*4];

void build(int id,int l,int r)

{

tree[id].left = l;tree[id].right = r;

if(l == r) { tree[id].val = val[l]; return ; }

int mid = (l + r) >>1;

build(id<<1,l,mid);build(id<<1|1,mid+1,r);

tree[id].val = max(tree[id<<1].val,tree[id<<1|1].val);

}

int query(int id,int l,int r)

{

if(l == tree[id].left && tree[id].right == r) return tree[id].val;

int mid = (tree[id].left + tree[id].right) >>1;

if(l > mid) return query(id<<1|1,l,r);

if(r <= mid) return query(id<<1,l,r);

return max(query(id<<1,l,mid),query(id<<1|1,mid+1,r));

}

inline int find(int x)

{

int l = 1,r = n,mid,num;

while(l <= r)

{

if(id[mid = (l+r)>>1] == x) return mid;

else if(id[mid] < x) l = mid + 1;

else r = mid - 1;

}

return l;

}

int main()

{

read(n);

int x,y;

rep(i,1,n)

{

read(x);read(y);

id[i] = x;val[i] = y;

}

build(1,1,n);

read(m);

while(m--)

{

bool e = 0;

read(y); read(x);

if(y > x) { puts("false");continue; }

if(x == y) { puts("true");continue; }

int Y = find(y), X = find(x);int Z = Y;

if(id[X] != x){

if(Y + 1 <= X - 1 && id[Y] == y) puts(query(1,Y+1,X-1) >= val[Y] ? "false":"maybe");

else puts("maybe");

continue;

}

if(y == id[Y]){

if(val[Y] < val[X]) { puts("false");continue; }

++Y;

}else e = 1;

if(X == Y){ puts(x - y == X - Z ?"true":"maybe"); continue; }

int ans = query(1,Y,X-1);

puts(val[X] <= ans?"false":x - y == X - Z && !e ?"true":"maybe");

}

return 0;

}

2017年8月20日 1,067 0 /

BZOJ

Tag: 二分答案线段树

疫情控制 NOIP2012 T6

二分答案 + 贪心；

你会发现，其实对于每个点，我们只要能往上（不是根节点）一定是更优的，如果是根节点，我们先看看这个点通不通，不通的话这个点判通，返回，不然的话进入根节点找最小不通的点。

最后一个点恶心的菊花图，所以对于这道题的极限数据，你倍增不倍增都没卵用，我也懒得帖我倍增+桶排的代[......]

2017年7月3日 1,180 0 /

Luogu NOIP/NOI

Tag: 二分答案倍增贪心法