bzoj2527 [Poi2011]Meteors

传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2527

【题解】

整体二分思想,其实就是把一坨二分拿一起处理了。。。

(事实上这题暴力好像。。不需要二分?)

我们定义solve(l,r,al,ar)为当前二分区间为[l,r],在这个区间的公司为id[al..ar]

那么我们每次把l..mid的操作做一下,然后依次判断每个公司是否满足了条件,满足就说明答案在[l,mid],归到左半区间;否则就说明答案在[mid+1,r],归到右半区间。

归到某个区间实际上就是给al...ar重标号,使得有amid,al...amid被划分到左边,amid+1...ar被划分到右边。

递归solve(l,mid,al,amid),solve(mid+1,r,amid+1,ar)即可。

# 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];

int head[M], nxt[M], to[M], tot=0;
inline void add(int u, int v) {
    ++tot; nxt[tot] = head[u]; head[u] = tot; to[tot] = 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]);
        add(bel[i], 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;
}

时间: 06-04

bzoj2527 [Poi2011]Meteors的相关文章

[Poi2011]Meteors 题解

题目大意: 给定一个环,每个节点有一个所属国家,k次事件,每次对[l,r]区间上的每个点点权加上一个值,求每个国家最早多少次操作之后所有点的点权和能达到一个值. 思路: 整体二分(二分答案),对于每个国家,如果在m次事件后到达目标则放在左边,否则放在右边(用下标映射).区间加用树状数组维护. 反思: 整体二分不熟练.二分计算时算到mid,now表示当前已经经历了几次事件(可进可退).快速排序用的也是整体二分. 代码: 1 #include<cstdio> 2 #define ll long l

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.总木

BZOJ 2525 [Poi2011]Dynamite 二分+树形贪心

题意: n个点,一棵树,有些点是关键点,可以将m个点染色. 求所有关键点到最近的被染色点的距离的最大值最小. 解析: 反正从这道题我是学了一种做题思路? 大爷讲课的时候说的:一般选择某些点的代价相同的话都是贪心,代价不同的话一般都是DP. 想想也挺对的,不过就是没有感悟到过? 反正这题考试的时候我是直接D了贪心的- -! 忘了为啥D了. 显然最大值最小我们需要二分一下这个值. 然后接下来我们从下往上扫整棵树. 节点的状态有几个? 第一种是 子树内没有不被覆盖的关键点,并且子树中有一个节点的贡献可

BZOJ2280 [Poi2011]Plot

恩..这题真是sxbk 我们先二分答案,然后判断答案是否满足要求 判断方法是二分当前段的长度一直做到底,当然我们可以用倍增这样快一点,直接随机增量就可以了 然后就是卡常..... 然后就是卡进度QAQQQQQQQ没了 1 /************************************************************** 2 Problem: 2280 3 User: rausen 4 Language: C++ 5 Result: Accepted 6 Time:90

BZOJ2276: [Poi2011]Temperature

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