资源描述：
《hdu 树状数组 区间更新及点询问》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、HDU4031树状数组区间更新及点询问/*******************************************************************************去年成都赛区网络赛一道题，树状数组在区间更新中的应用。树状数组一般支持的是改点，查区间，但是这道题要求的是改区间，查点，这就要变通一下，具体可以看代码，另外要考虑的一个问题是，如何统计？这里的处理方法就是把总共的攻击次数-防御的次数，因为对单个点的询问可能有多次，所以为每个点都设定一个游标来优化时间～*****************************
2、**************************************************/#include#include#include#include#include#include#include#include#include#include#include#include#include#include#int,s)memcpy((t),(s),sizeof(s))#defineSC(t,s)static_cast(s)#defineLEN(s)static_cast(strlen((s)))#defineSZ(s)static_
3、cast((s).size()) typedefdoubleLF;typedef__int64LL;//VCtypedefunsigned__int64ULL; typedefpairPII;typedefpairPLL;typedefpairPDD; typedefvectorVI;typedefvectorVC;typedefvectorVF;typedefvectorVS; templateTsqa(constT&x){returnx*x;}templateTll(constT&x){returnxtemplateTrr(constT&x){re
4、turnxtemplateTgcd(Ta,Tb){if(!a
5、
6、!b){returnmax(a,b);}Tt;while(t=a%b){a=b;b=t;}returnb;}; constintINF_INT=0x3f3f3f3f;constLLINF_LL=0x7fffffffffffffffLL;//15fconstdoubleoo=10e9;constdoubleeps=10e-7;constdoublePI=acos(-); #defineONLINE_JUDGE constintMAXN=20004; inttest,n,q,t;inttree
7、[MAXN];intcrs[MAXN],def[MAXN];vectorvp; voidupdateBIT(intx,intinc){for(inti=x;i>0;i-=LOWBIT(i)){tree[i]+=inc;}return;}voidupdateSeg(intl,intr,intinc){updateBIT(l-1,-inc);updateBIT(r,inc);return;}intqueryBIT(intx){intsum=0;for(inti=x;i{sum+=tree[i];}returnsum;}voidace(){intcas=1;
8、charop[10];intl,r,p;for(scanf(“%d”,&test);test--;++cas){scanf(“%d%d%d”,&n,&q,&t);CLR(tree,0);CLR(crs,0);CLR(def,0);();intind=0;printf(“Case%d:”,cas);while(q--){scanf(“%s”,op);if(‘A’==op[0]){scanf(“%d%d”,&l,&r);if(l>r){swap(l,r);}//l=max(l,1);//r=min(r,n);updateSeg(l,r,1);_back
9、(PII(l,r));++ind;}else{scanf(“%d”,&p);if(1==t){puts(“0”);continue;}inttoken=0;while(crs[p]{if(vp[crs[p]].first{if(0==token%t){crs[p]+=t-1;++def[p];token=t-1;}++token;}++crs[p];}printf(“%d”,queryBIT(p)-def[p]);}}}return;}intmain(){#ifndefONLINE_JUDGEfreopen(““,“r”,stdin);freope
10、n(““,“w”,stdout);#endiface();return0;}/********
