M_sea

洛谷3527 [POI2011]MET-Meteors
LuoguBZOJ权限题分析整体二分。显然,对于一个国家,可以二分哪一次流星雨后收集够了。但是现在有多个国家,可以...
扫描右侧二维码阅读全文
21
2018/12

洛谷3527 [POI2011]MET-Meteors

Luogu

BZOJ权限题

分析

整体二分。

显然,对于一个国家,可以二分哪一次流星雨后收集够了。但是现在有多个国家,可以放在一起来二分。

用一个资瓷区间修改、单点查询的树状数组来维护就行。

有一个小优化,可以不开long long,详见代码。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int MAXN=600010;

int n,m,k;
struct query { int type,l,r,w,id; }; //type:0是任务,1是l<=r的流星雨,2是l>r的流星雨
query q[MAXN],lq[MAXN],rq[MAXN];
vector<int> s[MAXN];
int p[MAXN];
int ans[MAXN];

int c[MAXN];
#define lowbit(x) (x&-x)
inline void add(int x,int y) { while (x<=m) c[x]+=y,x+=lowbit(x); }
inline int sum(int x) { int y=0; while (x) y+=c[x],x^=lowbit(x); return y; }

inline void solve(int lval,int rval,int st,int ed) {
    if (st>ed) return;
    if (lval==rval) {
        for (re int i=st;i<=ed;++i)
            if (!q[i].type) ans[q[i].id]=lval;
        return;
    }
    int mid=(lval+rval)>>1,lt=0,rt=0;
    for (re int i=st;i<=ed;++i) {
        if (!q[i].type) { //查询
            int ss=0;
            for (re int j=0;j<s[q[i].id].size();++j) {
                ss+=sum(s[q[i].id][j]);
                if (ss>=q[i].w) break; //小小的优化一下
            }
            if (ss>=q[i].w) lq[++lt]=q[i];
            else q[i].w-=ss,rq[++rt]=q[i];
        } else { //修改
            if (q[i].id<=mid) {
                if (q[i].type==1)
                    add(q[i].l,q[i].w),add(q[i].r+1,-q[i].w);
                else
                    add(1,q[i].w),add(q[i].r+1,-q[i].w),add(q[i].l,q[i].w);
                lq[++lt]=q[i];
            }
            else rq[++rt]=q[i];
        }
    }
    for (re int i=st;i<=ed;++i)
        if (q[i].id<=mid&&q[i].type) {
            if (q[i].type==1)
                add(q[i].l,-q[i].w),add(q[i].r+1,q[i].w);
            else
                add(1,-q[i].w),add(q[i].r+1,q[i].w),add(q[i].l,-q[i].w);
        }
    for (re int i=1;i<=lt;++i) q[st+i-1]=lq[i];
    for (re int i=1;i<=rt;++i) q[st+lt+i-1]=rq[i];
    solve(lval,mid,st,st+lt-1); solve(mid+1,rval,st+lt,ed);
}

int main() {
    n=read(),m=read();
    for (re int i=1;i<=m;++i) s[read()].push_back(i);
    for (re int i=1;i<=n;++i) p[i]=read();
    k=read();
    for (re int i=1;i<=k;++i) {
        q[i].l=read(),q[i].r=read(),q[i].w=read(),q[i].id=i;
        if (q[i].l<=q[i].r) q[i].type=1;
        else q[i].type=2;
    }
    for (re int i=1;i<=n;++i)
        q[k+i].type=0,q[k+i].w=p[i],q[k+i].id=i;
    solve(1,k+1,1,k+n);
    for (re int i=1;i<=n;++i) {
        if (ans[i]!=k+1) printf("%d\n",ans[i]);
        else puts("NIE");
    }
    return 0;
}
最后修改:2019 年 01 月 03 日 02 : 02 PM

发表评论