2 75971 poao899 49440K 4656MS G++ 3.16K 2010-04-26 08:47:55 .
Inspired by warehouse?
不過三維作法很有趣，竟然有一個n維曼哈頓轉
Chebyshev distance的作法，
可惜依現在硬體技術，作用有限
事實上這兩個都有優點，可惜自由轉換僅限於1或2維
算是個遺憾吧(?
//*****************************************
#include<algorithm>
#define N 100010
#define lb(x) ((x)&-(x))
struct ele{
int i, j, k, w, x, y, z;
void _2get();
void _3get();
}_ar[N];
int ar[N], front, rear;
int b, n, d, m, nmax; long long ans;
int getint(){
int g=0; char c=getchar();
while(c==10||c==32||c==9)c=getchar();
while(c>='0'&&c<='9'){
g= g*10+c-48;
c=getchar();
}
return g;
}
//case 2
#define _2LEN 75010
void ele::_2get(){
i= getint(); j= getint();
x= i+j; y= i-j;
}
bool _2cmp(ele a, ele b){
return a.y<b.y;
}
int _2bit[_2LEN*3];
inline int _2qry(int a){
if(a<0) return 0;
int ret= 0;
while(a>0){
ret+= _2bit[a];
a-= lb(a);
}
return ret;
}
inline int _2find(int l, int r){
return _2qry(r)-_2qry(l-1);
}
inline void _2adj(int a, int r){
while(a<=nmax){
_2bit[a]+= r;
a+= lb(a);
}
}
//case 3
#define _3LEN 76
void ele::_3get(){
i= getint(); j= getint(); k= getint();
w= i-j-k; x= i+j-k+m; y= i-j+k+m; z= i+j+k;
}
bool _3cmp(ele a, ele b){
return a.w<b.w;
}
int _3bit[_3LEN*3+1][_3LEN*3+1][_3LEN*3+1];
inline int _3qry(int x, int y, int z){
int ret= 0;
for(int xx=x; xx>0; xx-=lb(xx))
for(int yy=y; yy>0; yy-=lb(yy))
for(int zz=z; zz>0; zz-=lb(zz))
ret+= _3bit[xx][yy][zz];
return ret;
}
inline int _3find(int lx, int ly, int lz, int rx, int ry, int rz){
if(rx> nmax)rx= nmax;
if(ry> nmax)ry= nmax;
if(rz> nmax)rz= nmax;
int ret= _3qry(rx,ry,rz);
ret= ret- _3qry(lx-1,ry,rz)- _3qry(rx,ly-1,rz)- _3qry(rx,ry,lz-1);
ret= ret+ _3qry(rx,ly-1,lz-1)+ _3qry(lx-1,ry,lz-1)+ _3qry(lx-1,ly-1,rz);
ret= ret- _3qry(lx-1,ly-1,lz-1);
return ret;
}
inline void _3adj(int x, int y, int z, int r){
for(int xx=x; xx<=nmax; xx+=lb(xx))
for(int yy=y; yy<=nmax; yy+=lb(yy))
for(int zz=z; zz<=nmax; zz+=lb(zz))
_3bit[xx][yy][zz]+= r;
}
int main(){
b= getint(); n= getint(); d= getint(); m= getint();
//case 1
if(b==1){
for(int i=0; i<n; i++) ar[i]= getint();
std::sort(ar, ar+n);
for(front=rear=0; rear<n; rear++){
while(ar[front]+d< ar[rear]) front++;
ans+= rear-front;
}
}
//case 2
else if(b==2){
nmax= _2LEN*3;
for(int i=0; i<n; i++) _ar[i]._2get();
std::sort(_ar, _ar+n, _2cmp);
for(front=rear=0; rear<n; rear++){
while(_ar[front].y+d< _ar[rear].y){
_2adj(_ar[front].x, -1);
front++;
}
ans+= _2find(_ar[rear].x-d, _ar[rear].x+d);
_2adj(_ar[rear].x, 1);
}
}
//case 3
else if(b==3){
nmax= _3LEN*3;
for(int i=0; i<n; i++) _ar[i]._3get();
std::sort(_ar, _ar+n, _3cmp);
for(front=rear=0; rear<n; rear++){
while(_ar[front].w+d< _ar[rear].w){
_3adj(_ar[front].x, _ar[front].y, _ar[front].z, -1);
front++;
}
ans+= _3find(_ar[rear].x-d, _ar[rear].y-d, _ar[rear].z-d, _ar[rear].x+d, _ar[rear].y+d, _ar[rear].z+d);
_3adj(_ar[rear].x, _ar[rear].y, _ar[rear].z, 1);
}
}
printf("%I64d\n", ans);
}
