#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
#define F first
#define S second
#define MAX_N 150005
#define B 1000
int n,k,bs[MAX_N/B+1],p[MAX_N],l,cnt,ds[MAX_N/B+1][B*2+1],sz[MAX_N/B+1][B*2+1];
P id[MAX_N],el[MAX_N/B+1][B*2+1],pl[MAX_N];
void Bini(P *xel,int xbs,int *xds,int *xsz){
sort(xel,xel+xbs);
for(int i=0;i<xbs;i++)id[xel[i].S]=P(x,i);
int r=xbs;
for(int i=xbs-1;i>=0;i--){
while(r-1>=0&&xel[i].F+l<xel[r-1].F)r--;
if(r==xbs){
xds[i]=xel[i].F+l;
xsz[i]=1;
}else{
xds[i]=xds[r];
xsz[i]=xsz[r]+1;
}
}
}
void ALLini(void){
for(int i=0;i<n;i++)pl[i]=P(p[i],i);
sort(pl,pl+n);
bs[0]=0;
k=0;
for(int i=0;i<n;i++){
if(bs[k]>=B){
k++;
bs[k]=0;
}
el[k][bs[k]]=pl[i];
id[pl[i].S]=P(k,bs[k]);
bs[k]++;
}
for(int i=0;i<=k;i++)Bini(el[i],bs[i],ds[i],sz[i]);
}
void init(int N, int L, int X[]){
n=N,l=L;
for(int i=0;i<n;i++)p[i]=X[i];
ALLini();
}
int update(int t, int y){
int a=id[t].F,b=id[t].S;
if(b!=bs[a]-1)el[a][b]=el[a][bs[a]-1];
bs[a]--;
Bini(el[a],bs[a],ds[a],sz[a]);
p[t]=y;
a=-1;
while(a+1<=k&&bs[a+1]==0||(bs[a+1]>=1&&el[a+1][0].F<=y)){
a++;
}
if(a==-1)a=0;
el[a][bs[a]]=P(y,t);
bs[a]++;
Bini(el[a],bs[a],ds[a],sz[a]);
int ans=0;
a=0,b=-1;
for(;a<=k;a++){
if(bs[a]==0)continue;
int c=upper_bound(el[a],el[a]+bs[a],P(b,n))-el[a];
if(c==bs[a])continue;
ans+=sz[a][c];
b=ds[a][c];
}
cnt++;
if(cnt>=B){
cnt=0;
ALLini();
}
return ans;
}
Compilation message
elephants.cpp: In function 'void Bini(P*, int, int*, int*)':
elephants.cpp:13:39: error: 'x' was not declared in this scope
for(int i=0;i<xbs;i++)id[xel[i].S]=P(x,i);
^
elephants.cpp: In function 'int update(int, int)':
elephants.cpp:54:14: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
while(a+1<=k&&bs[a+1]==0||(bs[a+1]>=1&&el[a+1][0].F<=y)){
~~~~~~^~~~~~~~~~~~
