Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 整体二分真的不知道怎么WA了

Posted by Robert_Yuan at 2016-03-03 10:00:49 on Problem 2104 and last updated at 2016-03-03 21:58:20
```本机和已经A了的主席树对拍。

【附代码】
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int maxn=100010;
const int INF=2*1e9;

struct Query{
int x,y,k,id,cur;
bool tp;
}q[maxn<<1],q1[maxn<<1],q2[maxn<<1];

int n,m,tot;
int ans[maxn],a[maxn],b[maxn],tmp[maxn<<1];

for(;x<=n;x+=x&-x) b[x]+=d;
}

int sum=0;
for(int i=x;i;i-=i&-i) sum+=b[i];
return sum;
}

void div(int H,int T,int l,int r){
if(H>T) return ;
if(l==r){
for(int i=H;i<=T;i++)
if(!q[i].tp) ans[q[i].id]=l;
return ;
}
int mid=(l+r)>>1;
for(int i=H;i<=T;i++){
else if(!q[i].tp)
}
for(int i=H;i<=T;i++)
int l1=0,l2=0;
for(int i=H;i<=T;i++){
if(q[i].tp){
if(q[i].y<=mid) q1[++l1]=q[i];
else q2[++l2]=q[i];
}
else{
if(q[i].cur+tmp[i]>=q[i].k) q1[++l1]=q[i];
else
q[i].cur+=tmp[i],q2[++l2]=q[i];
}
}
for(int i=1;i<=l1;i++) q[H+i-1]=q1[i];
for(int i=1;i<=l2;i++) q[H+l1+i-1]=q2[i];
div(H,H+l1-1,l,mid);
div(H+l1,T,mid+1,r);
}

int main(){
#ifndef ONLINE_JUDGE
freopen("2104.in","r",stdin);
freopen("2104.out","w",stdout);
#endif

int l,r,k;

scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
q[++tot].tp=1;q[tot].x=i;q[tot].y=a[i];
}
for(int i=1;i<=m;i++){
tot++;
scanf("%d%d%d",&q[tot].x,&q[tot].y,&q[tot].k);
q[tot].id=i;
}
div(1,tot,0,INF);
for(int i=1;i<=m;i++)
printf("%d\n",ans[i]);

return 0;
}```

Followed by: