# bzoj2527 [Poi2011]Meteors

【题解】

（事实上这题暴力好像。。不需要二分？）

```# include <stdio.h>
# include <string.h>
# include <iostream>
# include <algorithm>
// # include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int M = 3e5 + 10;
const int mod = 1e9+7;
const int INF = 1e9;

# define RG register
# define ST static

int n, m, Q;
int bel[M];
struct quest {
int L, R, A;
quest() {}
quest(int L, int R, int A) : L(L), R(R), A(A) {}
}q[M];

inline void add(int u, int v) {
}

// 区间修改，单点查询
struct BIT {
int n;
ll c[M << 1];
# define lb(x) (x&(-x))
inline void set(int _n) {
n = _n;
memset(c, 0, sizeof c);
}
inline void edt(int x, ll d) {
for (; x<=n; x+=lb(x)) c[x] += d;
}
inline void edt(int x, int y, ll d) {
edt(x, d); edt(y+1, -d);
}
inline ll sum(int x) {
ll ret = 0;
for (; x; x-=lb(x)) ret += c[x];
return ret;
}
}T;

int a[M];
ll s[M];
int id[M], t1[M], t2[M];
int ans[M];
inline void solve(int l, int r, int al, int ar) {
if(al > ar) return;
if(l == r) {
for (int i=al; i<=ar; ++i) ans[id[i]] = l;
return ;
}
int mid = l+r>>1;
for (int i=l; i<=mid; ++i) {
if(q[i].L <= q[i].R) T.edt(q[i].L, q[i].R, q[i].A);
else T.edt(1, q[i].R, q[i].A), T.edt(q[i].L, m, q[i].A);
}
ll cur;    bool ok;
int t1n, t2n, tn; t1n = t2n = 0;
for (int i=al; i<=ar; ++i) {
int x = id[i];
ok = 0, cur = s[x];
for (int j=head[x]; j; j=nxt[j]) {
cur += T.sum(to[j]);
if(cur >= a[x]) {
ok = 1;
break;
}
}
if(ok) t1[++t1n] = x;
else t2[++t2n] = x, s[x] = cur;
}
for (int i=l; i<=mid; ++i) {
if(q[i].L <= q[i].R) T.edt(q[i].L, q[i].R, -q[i].A);
else T.edt(1, q[i].R, -q[i].A), T.edt(q[i].L, m, -q[i].A);
}
tn = al-1;
for (int i=1; i<=t1n; ++i) id[++tn] = t1[i];
t1n = tn;
for (int i=1; i<=t2n; ++i) id[++tn] = t2[i];
solve(l, mid, al, t1n);
solve(mid+1, r, t1n+1, ar);
}

int main() {
cin >> n >> m;
for (int i=1; i<=m; ++i) {
scanf("%d", &bel[i]);
}
for (int i=1; i<=n; ++i) scanf("%d", &a[i]), id[i] = i;
cin >> Q;
for (int i=1; i<=Q; ++i) scanf("%d%d%d", &q[i].L, &q[i].R, &q[i].A);
q[++Q] = quest(1, m, INF);
T.set(m+1);
solve(1, Q, 1, n);
for (int i=1; i<=n; ++i)
if(ans[i] == Q) puts("NIE");
else printf("%d\n", ans[i]);
return 0;
}```

## BZOJ 2527 [Poi2011]Meteors（整体二分）

[题目链接] http://www.lydsy.com/JudgeOnline/problem.php?id=2527 [题目大意] 有N个成员国.现在它发现了一颗新的星球, 这颗星球的轨道被分为M份(第M份和第1份相邻),第i份上有第Ai个国家的太空站. 这个星球经常会下陨石雨.BIU已经预测了接下来K场陨石雨的情况. BIU的第i个成员国希望能够收集Pi单位的陨石样本. 你的任务是判断对于每个国家,它需要在第几次陨石雨之后,才能收集足够的陨石. [题解] 如果枚举每场陨石雨,树状数组查询每个

## BZOJ2212: [Poi2011]Tree Rotations

2212: [Poi2011]Tree Rotations Time Limit: 20 Sec  Memory Limit: 259 MBSubmit: 391  Solved: 127[Submit][Status] Description Byteasar the gardener is growing a rare tree called Rotatus Informatikus. It has some interesting features: The tree consists o

## 【BZOJ2216】[Poi2011]Lightning Conductor 决策单调性

[BZOJ2216][Poi2011]Lightning Conductor Description 已知一个长度为n的序列a1,a2,...,an.对于每个1<=i<=n,找到最小的非负整数p满足 对于任意的j, aj < = ai + p - sqrt(abs(i-j)) Input 第一行n,(1<=n<=500000)下面每行一个整数,其中第i行是ai.(0<=ai<=1000000000) Output n行,第i行表示对于i,得到的p Sample I

## BZOJ2213: [Poi2011]Difference

2213: [Poi2011]Difference Time Limit: 10 Sec  Memory Limit: 32 MBSubmit: 343  Solved: 108[Submit][Status] Description A word consisting of lower-case letters of the English alphabet ('a'-'z') is given. We would like to choose a non-empty contiguous (

## 【BZOJ2529】[Poi2011]Sticks 贪心

[BZOJ2529][Poi2011]Sticks Description 给出若干木棍,每根木棍有特定的颜色和长度.问能否找到三条颜色不同的木棍构成一个三角形.(注意这里所说的三角形面积要严格大于0) 第一行给出一个整数k(3<=k<=50),表示颜色的种数.这k种颜色被标号为1至k.接下来k行,第i+1描述颜色为i的木棍的信息.首先一个整数Ni(1<=Ni<=10^6)表示颜色为i的木棍的数量.接下来Ni个整数,表示这Ni根木棍各自的长度.所有木棍的长度<=10^9.总木

## BZOJ2276: [Poi2011]Temperature

n<=1000000个数,每个数的选择范围在Li到Ri<=1000000000之间,求最长能得到多长的连续不下降序列. 首先可以暴力,f[i][j]表示前i个数,最后一个数取j,然后瞎转移就好了,显然过不了. 仔细一想,转移过来的状态只有几个,用{x,y}表示一个路径,最后一个数为x,答案为y.x越大,y应该越大.而每次扫到一个新区间,要新开点的话,肯定选最小的点新开.于是就变成这样: 右边那个圈状态更新答案然后删掉,左边那个圈记y的最大值Max然后丢给{ai,Max},加进去. 区间操作用线