17网站一起做网店增城,泉州网站制作维护,网站404网页界面psd源文件模板,网页布局技巧传送门
题意#xff1a;动态加点#xff0c;给定点询问曼哈顿距离最近的点 N,M≤3e5,x,y≤1e6N,M \leq 3e5,x,y \leq 1e6N,M≤3e5,x,y≤1e6
经(kan)过(le)分(ti)析(jie),这是一道cdqcdqcdq分治
考虑当前区间左半边修改对右半边的询问的影响
设左边某个修改为(x1,y1)(x_1,…传送门
题意动态加点给定点询问曼哈顿距离最近的点
N,M≤3e5,x,y≤1e6N,M \leq 3e5,x,y \leq 1e6N,M≤3e5,x,y≤1e6
经(kan)过(le)分(ti)析(jie),这是一道cdqcdqcdq分治
考虑当前区间左半边修改对右半边的询问的影响
设左边某个修改为(x1,y1)(x_1,y_1)(x1,y1)右边的某个询问为(x2,y2)(x_2,y_2)(x2,y2)
考虑x1≤x2,y1≤y2x_1 \leq x_2,y_1 \leq y_2x1≤x2,y1≤y2的情况,答案为x2y2−x1−y1x_2y_2-x_1-y_1x2y2−x1−y1
因为坐标是线性级别所以需要排序搞掉一维
左右分别以xxx坐标排序
这样可以用双指针搞掉xxx的限制
yyy坐标开个树状数组记录不超过yyy的修改中最大的xyxyxy
然后很容易计算答案
其他三种情况类似
为了实现方便直接旋转坐标系即用infinfinf减
树状数组已经有了logloglog我们已经无所畏惧所以可以直接sortsortsort
复杂度O(NlogN2)O(Nlog_N^2)O(NlogN2)
#include iostream
#include cstdio
#include cstring
#include cctype
#include algorithm
#define MAXN 600005
#define MAXM 2000005
#define MAX 1000000
using namespace std;
inline int read()
{int ans0;char cgetchar();while (!isdigit(c)) cgetchar();while (isdigit(c)) ans(ans3)(ans1)(c^48),cgetchar();return ans;
}
int n,m,siz;
struct BIT
{int s[MAXM];inline int lowbit(const int x){return x-x;}inline void modify(int x,const int v){for (;x(MAX1);s[x]max(s[x],v),xlowbit(x));}inline int query(int x){int ans-0x3f3f3f3f;for (;x;ansmax(ans,s[x]),x-lowbit(x));return ans;}inline void clear(int x){for (;x(MAX1);s[x]-0x3f3f3f3f,xlowbit(x));}
}bit;
int ans[MAXN];
struct query{int type,x,y,pos;}q[MAXN];
inline bool operator (const query a,const query b){if (a.xb.x) return a.yb.y;return a.xb.x;}
void calc(int l,int r)
{int nowl-1,mid(lr)1;for (int imid1;ir;i){if (q[i].type1) continue;while (nowmidq[now1].xq[i].x) {now;if (q[now].type1) bit.modify(q[now].y,q[now].xq[now].y);}ans[q[i].pos]min(ans[q[i].pos],q[i].xq[i].y-bit.query(q[i].y));}for (int il;imid;i) bit.clear(q[i].y);
}
void cdq(int l,int r)
{if (lr) return;int mid(lr)1;cdq(l,mid);cdq(mid1,r);calc(l,r);for (int il;ir;i) q[i].xMAX-q[i].x;sort(ql,qmid1),sort(qmid1,qr1);calc(l,r);for (int il;ir;i) q[i].yMAX-q[i].y;sort(ql,qmid1),sort(qmid1,qr1);calc(l,r);for (int il;ir;i) q[i].xMAX-q[i].x;sort(ql,qmid1),sort(qmid1,qr1);calc(l,r);for (int il;ir;i) q[i].yMAX-q[i].y;sort(ql,qr1);
}
int main()
{nread(),mread();for (int i1;in;i) q[i].type1,q[i].xread()1,q[i].yread()1;for (int i1;im;i) q[ni].typeread(),q[ni].xread()1,q[ni].yread()1,q[ni].posi;memset(ans,0x3f,sizeof(ans));for (int i0;iMAXM;i) bit.s[i]-0x3f3f3f3f;cdq(1,nm);for (int i1;im;i)if (ans[i]0x3f3f3f3f)printf(%d\n,ans[i]);return 0;
}
