HDU 4456 Crowd (cdq分治)

本文主要是介绍HDU 4456 Crowd (cdq分治)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

大意就是给出一个矩阵

初始每个位置上的值都为0

然后有两种操作

一种是更改某个位置上的值

另一个是求某个位置附近曼哈顿距离不大于K的所有位置的值的总和

网络上众多题解都是二维树状数组

但是这题也被认为是cdq分治的基础题

下面提供两种基于cdq分治的解法

解法一：

将所有点绕原点左旋45°

然后新的坐标也很好计算

x' = (x - y) * sqrt(2) / 2

y' = (x + y) * sqrt(2) / 2

由于都是小数

所以乘个sqrt(2) 就成整数了

即

x' = (x - y)

y' = x + y

由于x- y可能是负数。所以把点都右移一下 x' = x + y + n （n是矩阵宽度）然后矩阵的宽度和长度也就各自扩大了一倍

然后我们就可以惊奇的发现

原先是求 abs(x - x0) + abs(y - y0) <= k 的所有位置的值的和

现在变成了 abs(x' - x0') <= k 或者abs(y' - y0') <= k 就可以了

也就变成了求一个子矩阵的和

然后用CDQ分治维护一个普通矩阵的和，类似于经典题bzoj 2683

<span style="font-size:18px;"><span style="font-size:18px;">//      whn6325689
//		Mr.Phoebe
//		http://blog.csdn.net/u013007900
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>
#include <functional>
#include <numeric>
#pragma comment(linker, "/STACK:1024000000,1024000000")using namespace std;typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef complex<ld> point;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef vector<int> vi;#define CLR(x,y) memset(x,y,sizeof(x))
#define mp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define lowbit(x) (x&(-x))
#define MID(x,y) (x+((y-x)>>1))
#define eps 1e-9
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define LLINF 1LL<<62template<class T>
inline bool read(T &n)
{T x = 0, tmp = 1; char c = getchar();while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();if(c == EOF) return false;if(c == '-') c = getchar(), tmp = -1;while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();n = x*tmp;return true;
}
template <class T>
inline void write(T n)
{if(n < 0){putchar('-');n = -n;}int len = 0,data[20];while(n){data[len++] = n%10;n /= 10;}if(!len) data[len++] = 0;while(len--) putchar(data[len]+48);
}
//-----------------------------------const int MAXN=80010;struct Node
{int kind;int x,y,z,idx;Node(int k=0,int xx=0,int yy=0,int zz=0,int idx=0):kind(k),x(xx),y(yy),z(zz),idx(idx){}
}ask[4*MAXN],tmp1[4*MAXN],tmp2[4*MAXN];
int n,m,tot;
int c[MAXN];
int ans[MAXN];bool cmp(Node a,Node b)
{if(a.x==b.x)return a.y<b.y;return a.x<b.x;
}void update(int i,int v)
{for(;i<MAXN;i+=lowbit(i))c[i]+=v;
}int getsum(int i)
{int sum=0;for(;i;i-=lowbit(i))sum+=c[i];return sum;
}void clr(int i)
{for(;i<MAXN;i+=lowbit(i))c[i]=0;
}void change(int x,int y,int &xx,int &yy)
{xx=x-y+n;yy=x+y;
}void cdq(int l,int r)
{if(l==r)	return;int mid=MID(l,r);int l1=0,l2=0;cdq(l,mid);for(int i=l;i<=r;i++){if(i<=mid && ask[i].kind==1) tmp1[l1++]=ask[i];if(i> mid && ask[i].kind==2) tmp2[l2++]=ask[i];}sort(tmp1,tmp1+l1,cmp);sort(tmp2,tmp2+l2,cmp);for(int i=0,j=0;i<l2;i++){while(j<l1 && tmp1[j].x <= tmp2[i].x){update(tmp1[j].y,tmp1[j].z);j++;}ans[tmp2[i].idx]+=getsum(tmp2[i].y)*tmp2[i].z;}for(int i=0;i<l1;i++)clr(tmp1[i].y);cdq(mid+1,r);
}int main()
{
//    freopen("data.txt","r",stdin);
//    freopen("wa.txt","w",stdout);while(read(n)&&n){read(m);CLR(c,0);CLR(ans,0);CLR(ask,0);tot=0;for(int i=0,x,y,xx,yy,k,z;i<m;i++){read(k),read(x),read(y),read(z);change(x,y,xx,yy);if(k==1){tot++;ask[tot].kind=1;ask[tot].x=xx;ask[tot].y=yy;ask[tot].z=z;ask[tot].idx=i;}else{int x1=max(0,xx-z-1);int y1=max(0,yy-z-1);int x2=min(2*n,xx+z);int y2=min(2*n,yy+z);tot++;ask[tot].kind=2;ask[tot].x=x1;ask[tot].y=y1;ask[tot].z=1; ask[tot].idx=i;tot++;ask[tot].kind=2;ask[tot].x=x2;ask[tot].y=y1;ask[tot].z=-1;ask[tot].idx=i;tot++;ask[tot].kind=2;ask[tot].x=x1;ask[tot].y=y2;ask[tot].z=-1;ask[tot].idx=i;tot++;ask[tot].kind=2;ask[tot].x=x2;ask[tot].y=y2;ask[tot].z=1; ask[tot].idx=i;}}cdq(1,tot);for(int i=1;i<=tot;i++)if(ask[i].kind==2){printf("%d\n",ans[ask[i].idx]);i+=3;}}return 0;
}
</span></span>

解法二：

同样是子矩阵

但是可以用斜线法解答

省略了旋转的部分

但是cdq分治的部分略显麻烦

<span style="font-size:18px;"><pre name="code" class="cpp">//      whn6325689
//		Mr.Phoebe
//		http://blog.csdn.net/u013007900
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>
#include <functional>
#include <numeric>
#pragma comment(linker, "/STACK:1024000000,1024000000")using namespace std;typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef complex<ld> point;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef vector<int> vi;#define CLR(x,y) memset(x,y,sizeof(x))
#define mp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define lowbit(x) (x&(-x))
#define MID(x,y) (x+((y-x)>>1))
#define eps 1e-9
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define LLINF 1LL<<62template<class T>
inline bool read(T &n)
{T x = 0, tmp = 1; char c = getchar();while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();if(c == EOF) return false;if(c == '-') c = getchar(), tmp = -1;while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();n = x*tmp;return true;
}
template <class T>
inline void write(T n)
{if(n < 0){putchar('-');n = -n;}int len = 0,data[20];while(n){data[len++] = n%10;n /= 10;}if(!len) data[len++] = 0;while(len--) putchar(data[len]+48);
}
//-----------------------------------const int MAXN=80010;
const int POS=10000;struct Node
{int kind,idx;int x,y,z;
}ask[MAXN],tmp1[MAXN],tmp2[MAXN];
int n,m;
ll ans[MAXN],c[MAXN];bool cmp1(Node a,Node b)
{return a.x+a.y<=b.x+b.y;
}bool cmp2(Node a,Node b)
{return a.x+a.y+a.z<=b.x+b.y+b.z;
}bool cmp3(Node a,Node b)
{return a.x+a.y-a.z<=b.x+b.y-b.z;
}void update(int i,int v)
{for(;i<MAXN;i+=lowbit(i))c[i]+=v;
}ll getsum(int i)
{ll sum=0;for(;i>0;i-=lowbit(i))sum+=c[i];return sum;
}void clr(int i)
{for(;i<MAXN;i+=lowbit(i))c[i]=0;
}void cdq(int l,int r)
{if(l==r)	return;int mid=MID(l,r);int l1=0,l2=0;cdq(l,mid);for(int i=l;i<=r;i++){if(i<=mid && ask[i].kind==1) tmp1[l1++]=ask[i];else if(i> mid && ask[i].kind==2) tmp2[l2++]=ask[i];}sort(tmp1,tmp1+l1,cmp1);sort(tmp2,tmp2+l2,cmp2);for(int i=0,j=0;i<l2;i++){int lim=tmp2[i].x+tmp2[i].y+tmp2[i].z;while(j<l1 && tmp1[j].x+tmp1[j].y<=lim){update(tmp1[j].x-tmp1[j].y+POS,tmp1[j].z);j++;}ans[tmp2[i].idx]+=getsum(tmp2[i].x-tmp2[i].y+tmp2[i].z+POS)-getsum(tmp2[i].x-tmp2[i].y-tmp2[i].z-1+POS);}for(int i=0;i<l1;i++)clr(tmp1[i].x-tmp1[i].y+POS);sort(tmp2,tmp2+l2,cmp3);for(int i=0,j=0;i<l2;i++){int lim=tmp2[i].x+tmp2[i].y-tmp2[i].z-1;while(j<l1 && tmp1[j].x+tmp1[j].y<=lim){update(tmp1[j].x-tmp1[j].y+POS,tmp1[j].z);j++;}ans[tmp2[i].idx]-=getsum(tmp2[i].x-tmp2[i].y+tmp2[i].z+POS)-getsum(tmp2[i].x-tmp2[i].y-tmp2[i].z-1+POS);}for(int i=0;i<l1;i++)clr(tmp1[i].x-tmp1[i].y+POS);cdq(mid+1,r);
}int main()
{while(read(n)&&n){read(m);CLR(ans,0);CLR(c,0);for(int i=1;i<=m;i++){read(ask[i].kind),read(ask[i].x),read(ask[i].y),read(ask[i].z);ask[i].idx=i;}cdq(1,m);for(int i=1;i<=m;i++)if(ask[i].kind==2)printf("%lld\n",ans[i]);}return 0;
}
</span>