首页 > 代码库 > HDU 3854 Glorious Array(树状数组)
HDU 3854 Glorious Array(树状数组)
题意：给一些结点，每个结点是黑色或白色，并有一个权值。定义两个结点之间的距离为两个结点之间结点的最小权值当两个结点异色时，否则距离为无穷大。给出两种操作，一种是将某个结点改变颜色，另一个操作是询问当前距离小于K的结点有多少对，K是一个定值。
思路：先求最初时候小于k的结点有多少对，然后每次改变颜色的时候，统计该点左侧和右侧各有多少同色和异色的结点（这一步使用树状数组），分别处理就行。另外需要预处理离某个结点最近的两个距离小于K的结点的位置。
代码写的略乱。
#include<cstdio>#include<cstring>#include<algorithm>#include<vector>#include<time.h>#include<iostream>#define INF 10000000#define LL long longusing namespace std;int n,K;vector<int> vec;int col[100005];struct BIT{ int dat[100005]; void clear() { memset(dat,0,sizeof(dat)); } int lowBit(int x) { return -x&x; } int getSum(int x) { int s=0; while(x>0) { s+=dat[x]; x-=lowBit(x); } return s; } void addVal(int x,int c) { if(x<=0) return; while(x<=n) { dat[x]+=c; x+=lowBit(x); } } void setVal(int x,int c) { int old=getSum(x)-getSum(x-1); addVal(x,-old+c); } int getCol(int x) { return getSum(x)-getSum(x-1); } int countBlack(int ql,int qr) { if(qr<ql) return 0; return getSum(qr)-getSum(ql-1); } int countWhite(int ql,int qr) { if(qr<ql) return 0; int s=countBlack(ql,qr); return qr-ql+1-s; }};BIT tree;int leftM[100005],rightM[100005];int main(){ int T; scanf("%d",&T); while(T--) { int m; scanf("%d%d%d",&n,&m,&K); vec.clear(); for(int i=1; i<=n; ++i) { int val; scanf("%d",&val); if(val<K) vec.push_back(i); } tree.clear(); for(int i=1; i<=n; ++i) { int val; scanf("%d",&val); tree.setVal(i,val); int l=upper_bound(vec.begin(),vec.end(),i)-vec.begin()-1; int r=lower_bound(vec.begin(),vec.end(),i)-vec.begin(); if(l<0) leftM[i]=-1; else leftM[i]=vec[l]; if(r>=vec.size()) rightM[i]=-1; else rightM[i]=vec[r]; } LL sum=0; int last=1,end; for(int i=0; i<vec.size(); ++i) { last=(i==0)?1:vec[i-1]+1; end=(i==vec.size()-1)?n:vec[i+1]; LL lb=tree.countBlack(last,vec[i]-1),rw=tree.countWhite(vec[i]+1,n); LL lw=tree.countWhite(last,vec[i]-1),rb=tree.countBlack(vec[i]+1,n); sum+=lb*rw; sum+=lw*rb; int col=tree.getCol(vec[i]); if(col==0) sum+=lb+rb; else sum+=lw+rw; } while(m--) { int p; scanf("%d",&p); if(p==1) printf("%I64d\n",sum); else { int x; scanf("%d",&x); int old=tree.getCol(x); if(old==1) { if(leftM[x]!=-1) { LL lw,lb; if(leftM[x]==x) { lw=tree.countWhite(1,leftM[x]-1); lb=tree.countBlack(1,leftM[x]-1); } else { lw=tree.countWhite(1,leftM[x]); lb=tree.countBlack(1,leftM[x]); } sum-=lw; sum+=lb; } if(rightM[x]!=-1) { LL rw,rb; if(rightM[x]==x) { rb=tree.countBlack(rightM[x]+1,n); rw=tree.countWhite(rightM[x]+1,n); } else { rb=tree.countBlack(rightM[x],n); rw=tree.countWhite(rightM[x],n); } sum-=rw; sum+=rb; } } else { if(leftM[x]!=-1) { LL lw,lb; if(leftM[x]==x) { lw=tree.countWhite(1,leftM[x]-1); lb=tree.countBlack(1,leftM[x]-1); } else { lw=tree.countWhite(1,leftM[x]); lb=tree.countBlack(1,leftM[x]); } sum+=lw; sum-=lb; } if(rightM[x]!=-1) { LL rw,rb; if(rightM[x]==x) { rb=tree.countBlack(rightM[x]+1,n); rw=tree.countWhite(rightM[x]+1,n); } else { rb=tree.countBlack(rightM[x],n); rw=tree.countWhite(rightM[x],n); } sum+=rw; sum-=rb; } } tree.setVal(x,old^1); } } } return 0;}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。