HDU 5741 Helter Skelter(数形结合、二分)
题意:
$给定一个压缩过的0开头的01交替字符串,比如00110表示为\{ 2, 2, 1 \}$
$表示数字个数N\le 1000,x_i \le 10^6,Q\le 5\times 10^5次查询$
$每次给定a, b,问是否存在原串的子串0有a个,1有b个$
分析:
$我们把所有的a和b n^2枚举一下,如果把这些(a, b)表示在二维平面上$
$手玩一下可以发现[0\ldots 0]这种子串表示出来的(a, b)必然在图形的下部$
$也可以发现[1\ldots 1]这种子串表示出来的(a, b)必然在图形的下部$
$还可以发现图形是连通且封闭的,现在窝萌可以把这个图形抠出来一个凸包$
$假设这些下部点是红点,上部点是绿点,其它点是蓝点$
$画出一个图,然后根据性质抠一下就好了$
$红点在竖线的底端,绿点在竖线的顶端$
$之后对于每个询问,只要二分一下a,得到b的下界和上界,即可知道是否合法$
$时间复杂度O(n^2+qlogn^2)$
代码:
//
// Created by TaoSama on 2016-07-25
// Copyright (c) 2016 TaoSama. All rights reserved.
//
#pragma comment(linker, "/STACK:102400000,102400000")
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <vector>
using namespace std;
#define pr(x) cout << #x << " = " << x << " "
#define prln(x) cout << #x << " = " << x << endl
const int N = 1e3 + 10, INF = 0x3f3f3f3f, MOD = 1e9 + 7;
int n, m, a[N];
char ans[N * N];
int main() {
#ifdef LOCAL
freopen("C:\\Users\\TaoSama\\Desktop\\in.txt", "r", stdin);
// freopen("C:\\Users\\TaoSama\\Desktop\\out.txt","w",stdout);
#endif
ios_base::sync_with_stdio(0);
clock_t _ = clock();
/*
| ___B
| G ___| |
| ___| _____|
|___| |
| _____| R
| |
___|___|_____________
0|
*/
int t; scanf("%d", &t);
while(t--) {
scanf("%d%d", &n, &m);
for(int i = 0; i < n; ++i) scanf("%d", a + i);
vector<pair<int, int> > up, dw;
for(int i = 0; i < n; ++i) {
int zero = 0, one = 0;
for(int j = i; j < n; ++j) {
if(j % 2 == 0) zero += a[j];
else one += a[j];
//red points
if(i % 2 == 0 && j % 2 == 0) dw.push_back({zero, one});
//green points
if(i % 2 == 1 && j % 2 == 1) up.push_back({zero, one});
}
}
sort(dw.begin(), dw.end());
sort(up.begin(), up.end());
n = 0; //erase blues points, save lower red points
for(int i = 0, j; i < dw.size(); i = j) {
//jump vertical line
for(j = i; j < dw.size() && dw[j].first == dw[i].first; ++j);
//pop upper ones, save this lowest one
while(n > 0 && dw[n - 1].second >= dw[i].second) --n;
dw[n++] = dw[i];
}
dw.resize(n);
n = 0; //erase blues points, save upper green points
for(int i = 0, j; i < up.size(); i = j) {
//go vertical line's top
for(j = i; j < up.size() && up[j].first == up[i].first; ++j);
//if upper
if(!n || up[j - 1].second >= up[n - 1].second)
up[n++] = up[j - 1];
}
up.resize(n);
for(int i = 0; i < m; ++i) {
int a, b; scanf("%d%d", &a, &b);
auto st = lower_bound(dw.begin(), dw.end(), make_pair(a, -INF));
auto ed = upper_bound(up.begin(), up.end(), make_pair(a, +INF));
ans[i] = '0';
if(st != dw.end()) {
--ed;
if(b >= st->second && b <= ed->second) ans[i] = '1';
}
}
ans[m] = 0;
puts(ans);
}
#ifdef LOCAL
printf("\nTime cost: %.2fs\n", 1.0 * (clock() - _) / CLOCKS_PER_SEC);
#endif
return 0;
}
/*
dw:
3 0
up:
0 4
dw:
3 0
4 2
up:
0 2
dw:
3 0
4 2
6 3
7 7
8 11
10 12
up:
0 7
1 8
2 9
3 12
4 16
7 18
8 19
*/