首页 > 代码库 > Hdu 5032 Always Cook Mushroom (树状数组)
Hdu 5032 Always Cook Mushroom (树状数组)
题目大意:
在一个1000*1000的二维平面上,每一个整点都有一个权值,权值大小是 the production in the grid points (x, y) is (x + A)(y + B) where A, B are two constant.
思路分析:
先离线处理出所有的询问,对于每一个询问都有一个极角,按照极角排序。
然后对于平面上每一个点,都依次的加入到BIT中,当当前的这个询问的极角比这个点到原点的对应极角要大的时候,就将这个点加进去。
可以理解成有一根线,按照逆时针的方向在扫描整个二维平面,当这根线和某一个询问重合的时候,记录和,否则将扫过的所有点加入到BIT中。
#include <cstdio> #include <iostream> #include <cstring> #include <algorithm> #include <vector> #define lowbit(x) (x&(-x)) #define maxn 1005 using namespace std; typedef long long ll; int A,B; struct node { int r,c; double p; node(){} node(int _r,int _c,double _p):r(_r),c(_c),p(_p){} bool operator < (const node &cmp)const { return p<cmp.p; } }; vector <node> cq; struct line { int x,id; ll ans; double p; line(){} line(int _x,double _p):x(_x),p(_p){} bool operator < (const line &cmp)const { return p<cmp.p; } }; vector <line> scline; ll bit[1005]; bool cmp_id(line a,line b) { return a.id<b.id; } void update(int pos,ll val) { for(int x=pos;x<=1000;x+=lowbit(x)) bit[x]+=val; } ll query(int l,int r) { ll res=0; for(int x=r;x>=1;x-=lowbit(x))res+=bit[x]; ll ret=0; for(int x=l-1;x>=1;x-=lowbit(x))ret+=bit[x]; return res-ret; } int main() { int T,cas=1; cq.clear(); for(int i=1;i<=1000;i++) { for(int j=1;j<=1000;j++) { cq.push_back(node(i,j,1.0*i/j)); } } sort(cq.begin(),cq.end()); for(scanf("%d",&T);T--;) { scanf("%d%d",&A,&B); scline.clear(); int n; scanf("%d",&n); for(int i=0;i<n;i++) { int x,a,b; scanf("%d%d%d",&a,&b,&x); scline.push_back(line(x,1.0*b/a)); scline[i].id=i; } memset(bit,0,sizeof bit); sort(scline.begin(),scline.end()); int pos=0; for(int i=0;i<n;i++) { while(cq[pos].p<=scline[i].p) { update(cq[pos].c,(ll)(cq[pos].r+B)*(cq[pos].c+A)); pos++; } scline[i].ans=query(1,scline[i].x); } sort(scline.begin(),scline.end(),cmp_id); printf("Case #%d:\n",cas++); for(int i=0;i<n;i++) printf("%I64d\n",scline[i].ans); } return 0; }
Hdu 5032 Always Cook Mushroom (树状数组)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。