二分答案 – Tgotp-Blog

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日 341 0 /

poj

Tag: sa 二分答案

PHRASES - Relevant Phrases of Annihilation

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

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

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

搞定。

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

2017年12月21日 396 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日 590 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日 372 0 /

BZOJ

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

P2538 [SCOI2008]城堡

爆搜 + 贪心 + 二分 + floyd；

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

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

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

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

2017年9月27日 835 0 /

Luogu

Tag: floyd 二分答案期望

1014: [JSOI2008]火星人prefix

一脸萎靡。。。

这题做的疯。

数据真心有毒。

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

二分 + hash + splay

我只能说是个p的神题。

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

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

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

2017年9月22日 611 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日 958 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日 651 0 /

BZOJ

Tag: 二分答案线段树

疫情控制 NOIP2012 T6

二分答案 + 贪心；

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

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

2017年7月3日 682 0 /

Luogu NOIP/NOI

Tag: 二分答案倍增贪心法

聪明的质监员 NOIP2011

二分答案，sum[i]表示前i个中符合>=x的个数，num[i]表示前i个中这些符合的v之和；剩下的直接二分搞搞就好了。原谅sum与num的英语意义乱用2333.

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
typedef long long ll;
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 = 2e5+5;
int n ,m ,mid,sum[N];
ll num[N],ans = 1e16,y;
struct node{
	int w,v;
}a[N];
struct str{
	int l,r;
}p[N];
ll kk(ll x){ return x >= 0? x: -x; }
ll min(ll x,ll y){ return x > y? y : x; }
bool check(int x)
{
	ll z = 0;
	memset(num,0,sizeof(num)); memset(sum,0,sizeof(sum));
	for(int i = 1 ;i <= n; i++) { num[i] = num[i-1];sum[i] = sum[i-1]; if(a[i].w >= x) sum[i]++,num[i]+= a[i].v; }
	for(int i = 1 ;i <= m; i++)
		z += (sum[p[i].r] - sum[p[i].l - 1])*(num[p[i].r] - num[p[i].l - 1]);
	ans = min(ans,kk(z - y));
	if(z < y) return false;
	else return true;
}
int main()
{
	read(n);read(m);scanf("%lld",&y);
	int l = 0,r = 0;
	for(int i = 1 ;i <= n;i++) { read(a[i].w);read(a[i].v); r = max(r,a[i].w);  }
	for(int i = 1 ;i <= m;i++) { read(p[i].l);read(p[i].r); }
	while(l <= r)
	{
		if(check(mid = (l+r) >>1)) l = mid + 1;
		else r = mid - 1 ;
	}
	cout<<ans;
	return 0;
}

#include<iostream>

#include<cstring>

#include<algorithm>

#include<cstdio>

using namespace std;

typedef long long ll;

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 = 2e5+5;

int n ,m ,mid,sum[N];

ll num[N],ans = 1e16,y;

struct node{

int w,v;

}a[N];

struct str{

int l,r;

}p[N];

ll kk(ll x){ return x >= 0? x: -x; }

ll min(ll x,ll y){ return x > y? y : x; }

bool check(int x)

{

ll z = 0;

memset(num,0,sizeof(num)); memset(sum,0,sizeof(sum));

for(int i = 1 ;i <= n; i++) { num[i] = num[i-1];sum[i] = sum[i-1]; if(a[i].w >= x) sum[i]++,num[i]+= a[i].v; }

for(int i = 1 ;i <= m; i++)

z += (sum[p[i].r] - sum[p[i].l - 1])*(num[p[i].r] - num[p[i].l - 1]);

ans = min(ans,kk(z - y));

if(z < y) return false;

else return true;

}

int main()

{

read(n);read(m);scanf("%lld",&y);

int l = 0,r = 0;

for(int i = 1 ;i <= n;i++) { read(a[i].w);read(a[i].v); r = max(r,a[i].w); }

for(int i = 1 ;i <= m;i++) { read(p[i].l);read(p[i].r); }

while(l <= r)

{

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

else r = mid - 1 ;

}

cout<<ans;

return 0;

}

2017年7月3日 750 0 /

Luogu NOIP/NOI

Tag: 二分答案前缀和