HDU - 4456 cdq
发布时间:2020-12-14 04:18:42 所属栏目:大数据 来源:网络整理
导读:题意:给一个矩阵,两种操作1:修改单点的权值,2:查询和某个点曼哈顿距离小于r点的权值和 题解:先旋转坐标轴,(x,y)-(x-y,x+y)然后就变成了cdq分治裸题,子矩阵和和单点修改一维时间,二维xcdq,三维ybit //#pragma GCC optimize(2)//#pragma GCC optimize(3)//#pra
题意:给一个矩阵,两种操作1:修改单点的权值,2:查询和某个点曼哈顿距离小于r点的权值和 //#pragma GCC optimize(2) //#pragma GCC optimize(3) //#pragma GCC optimize(4) //#pragma GCC optimize("unroll-loops") //#pragma comment(linker,"/stack:200000000") //#pragma GCC optimize("Ofast,no-stack-protector") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") #include<bits/stdc++.h> #define fi first #define se second #define db double #define mp make_pair #define pb push_back #define pi acos(-1.0) #define ll long long #define vi vector<int> #define mod 1000000007 #define ld long double #define C 0.5772156649 #define ls l,m,rt<<1 #define rs m+1,r,rt<<1|1 #define pll pair<ll,ll> #define pil pair<int,ll> #define pli pair<ll,int> #define pii pair<int,int> //#define cd complex<double> #define ull unsigned long long #define base 1000000000000000000 #define Max(a,b) ((a)>(b)?(a):(b)) #define Min(a,b) ((a)<(b)?(a):(b)) #define fin freopen("a.txt","r",stdin) #define fout freopen("c.txt","w",stdout) #define fio ios::sync_with_stdio(false);cin.tie(0) template<typename T> inline T const& MAX(T const &a,T const &b){return a>b?a:b;} template<typename T> inline T const& MIN(T const &a,T const &b){return a<b?a:b;} inline void add(ll &a,ll b){a+=b;if(a>=mod)a-=mod;} inline void sub(ll &a,ll b){a-=b;if(a<0)a+=mod;} inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} inline ll qp(ll a,ll b){ll ans=1;while(b){if(b&1)ans=ans*a%mod;a=a*a%mod,b>>=1;}return ans;} inline ll qp(ll a,ll b,ll c){ll ans=1;while(b){if(b&1)ans=ans*a%c;a=a*a%c,b>>=1;}return ans;} using namespace std; const double eps=1e-8; const ll INF=0x3f3f3f3f3f3f3f3f; const int N=320000+10,maxn=200000+10,inf=0x3f3f3f3f; struct query{int op,x,y,z,id;}p[N]; bool cmp(const query&a,const query&b){return a.x<b.x || (a.x==b.x&&a.y<b.y);} int n,cnt,ans[N],res; struct bit{ int val[N]; void update(int i,int v) { for(;i<N;i+=i&(-i))val[i]+=v; } int query(int i) { int ans=0; for(;i;i-=i&(-i))ans+=val[i]; return ans; } }b; void cdq(int l,int r) { if(l==r)return ; int mid=(l+r)>>1; cdq(l,mid);cdq(mid+1,r); sort(p+l,p+mid+1,cmp);sort(p+mid+1,p+r+1,cmp); int le=l,ri=mid+1; while(ri<=r) { while(le<=mid&&p[le].op==2)le++; while(ri<=r&&p[ri].op==1)ri++; if(ri > r) break; if(le<=mid&&p[le].x<=p[ri].x)b.update(p[le].y,p[le].z),le++; else ans[p[ri].id]+=p[ri].z*b.query(p[ri].y),ri++; } le--; for(;le>=l;le--)if(p[le].op==1)b.update(p[le].y,-p[le].z); } int main() { while(~scanf("%d",&n)) { if(!n)break; scanf("%d",&m); cnt=res=0; for(int i=1;i<=m;i++) { ++cnt; scanf("%d%d%d%d",&p[cnt].op,&p[cnt].x,&p[cnt].y,&p[cnt].z); p[cnt].id=0; int x=p[cnt].x,y=p[cnt].y,z=p[cnt].z; p[cnt].x=x-y+n,p[cnt].y=x+y; x=p[cnt].x,y=p[cnt].y; if(p[cnt].op==2) { p[cnt].x=MIN(x+z,2*n + 5); p[cnt].y=MIN(y+z,2*n + 5); p[cnt].z=1; p[cnt].id=++res; ans[res] = 0; if(x-z-1>0) { ++cnt;p[cnt].id=res;p[cnt].op=2; p[cnt].x=x-z-1;p[cnt].y=y+z;p[cnt].z=-1; } if(y-z-1>0) { ++cnt;p[cnt].id=res;p[cnt].op=2; p[cnt].x=x+z;p[cnt].y=y-z-1;p[cnt].z=-1; } if(x-z-1>0&&y-z-1>0) { ++cnt;p[cnt].id=res;p[cnt].op=2; p[cnt].x=x-z-1;p[cnt].y=y-z-1;p[cnt].z=1; } } } // for(int i=1;i<=cnt;i++)printf("%d %d %d %d %dn",p[i].op,p[i].x,p[i].y,p[i].z,p[i].id); cdq(1,cnt); for(int i=1;i<=res;i++)printf("%dn",ans[i]); } return 0; } /******************** 8 5 1 8 8 1 1 1 1 -2 2 5 5 6 1 5 5 3 2 2 3 9 ********************/ (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |