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;
}