首页 > 代码库 > 线段树 FOJ 2174
线段树 FOJ 2174
FOJ 2174
区间跟新,区间询问:
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #define lson l,mid,rt<<1 5 #define rson mid+1,r,rt<<1|1 6 7 using namespace std; 8 typedef long long LL; 9 const int N=110001; 10 int sum[N<<2]; 11 int add[N<<2]; 12 13 void pushup(int rt){ 14 sum[rt]=sum[rt<<1]+sum[rt<<1|1]; 15 } 16 void pushdown(int l,int r,int rt){ 17 int mid=(l+r)>>1; 18 if(add[rt]!=0){ 19 add[rt<<1|1]+=add[rt]; 20 add[rt<<1]+=add[rt]; 21 sum[rt<<1]+=add[rt]*(mid-l+1); 22 sum[rt<<1|1]+=add[rt]*(r-mid); 23 add[rt]=0; 24 } 25 } 26 void updata(int L,int R,int a,int l,int r,int rt){ 27 if(L<=l&&r<=R){ 28 add[rt]+=a; 29 sum[rt]+=a*(r-l+1); 30 return; 31 } 32 pushdown(l,r,rt); 33 int mid=(l+r)>>1; 34 if(L<=mid) updata(L,R,a,lson); 35 if(mid<R) updata(L,R,a,rson); 36 pushup(rt); 37 } 38 void build(int l,int r,int rt){ 39 if(l==r){ 40 scanf("%d",&sum[rt]); 41 return ; 42 } 43 pushdown(l,r,rt); 44 int mid=(l+r)>>1; 45 build(lson); 46 build(rson); 47 pushup(rt); 48 } 49 int query(int L,int R,int l,int r,int rt){ 50 if(L<=l&&r<=R){ 51 return sum[rt]; 52 } 53 int ans=0; 54 pushdown(l,r,rt); 55 int mid=(l+r)>>1; 56 if(L<=mid) ans+=query(L,R,lson); 57 if(mid<R) ans+=query(L,R,rson); 58 return ans; 59 } 60 int main(){ 61 int n,m,q; 62 int x; 63 while(cin>>n>>m>>q){ 64 65 memset(add,0,sizeof(add)); 66 build(1,n,1); 67 for(int i=0;i<q;i++){ 68 scanf("%d",&x); 69 printf("%d\n",query(x,x+m-1,1,n,1)); 70 updata(x,x+m-1,-1,1,n,1); 71 } 72 } 73 74 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。