题解 P3527 【[POI2011]MET-Meteors】

1124828077ccj

2017-08-26 20:48:51

题解

这题是道二分题,然而二分很巧妙。

如果单个询问,显然可以O(logk)二分然后轻松判定。

但是多个询问就不好解决了,于是可以使用整体二分的思想。

我们可以二分k,然后可行的放一边,不可行的放另外一边

如何判定呢,树状数组扫过去就可以了,需要利用上一次的结果

然后分析一下时间复杂度

首先,二分和可行不可行的扫描合起来是O(mlogk)

然后树状数组每次扫过去的话,总共会把整个区间扫一遍(这个一指的是常数遍)

然后效率是O(n*logn*logn)

附代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cstdlib>
using namespace std;
int n,m,k,a[300002],s[300002],u[300002],v[300002],w[300002];
int t1[300002],t2[300002],p[300002],ans[300002],now;
long long f[300002];
vector<int>g[300002];
void gengxin(int x,int y){
    for (;x>=1;x-=x&-x)f[x]+=y;
}
long long chaxun(int x){
    long long ans=0;
    for (;x<=m;x+=x&-x)ans+=f[x];
    return ans;
}
bool pd(int a){
    long long ans=0;
    for (int i=0;i<g[a].size();i++)
    ans+=chaxun(g[a][i]);
    return ans>=s[a];
}
void ccj(int x,int y,int l,int r){//整体二分
    if (x>y)return;
    if (l==r){for (int i=x;i<=y;i++)ans[p[i]]=l;return;}
    int mid=(l+r)/2;
    while(now<mid)
    {
        now++;
        if (u[now]<=v[now])
        {
            gengxin(v[now],w[now]);gengxin(u[now]-1,-w[now]);
        }
        else
        {
            gengxin(m,w[now]);gengxin(u[now]-1,-w[now]);
            gengxin(v[now],w[now]);
        }
    }
    while(now>mid)
    {
        if (u[now]<=v[now])
        {
            gengxin(v[now],-w[now]);gengxin(u[now]-1,w[now]);
        }
        else
        {
            gengxin(m,-w[now]);gengxin(u[now]-1,w[now]);
            gengxin(v[now],-w[now]);
        }
        now--;
    }
    int l1=0,l2=0;
    for (int i=x;i<=y;i++)
    if (pd(p[i]))t1[++l1]=p[i];else t2[++l2]=p[i];
    for (int i=x;i<x+l1;i++)p[i]=t1[i-x+1];
    for (int i=x+l1;i<=y;i++)p[i]=t2[i-x-l1+1];
    ccj(x,x+l1-1,l,mid);ccj(x+l1,y,mid+1,r);
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++)
    {scanf("%d",&a[i]);g[a[i]].push_back(i);}
    for (int i=1;i<=n;i++)
    {p[i]=i;scanf("%d",&s[i]);}
    scanf("%d",&k);
    for (int i=1;i<=k;i++)
    scanf("%d%d%d",&u[i],&v[i],&w[i]);
    ccj(1,n,0,k+1);
    for (int i=1;i<=n;i++)
    if (ans[i]<=k)printf("%d\n",ans[i]);else puts("NIE");
    return 0;
}