来自 编程 2019-09-27 11:02 的文章
当前位置: 澳门三合彩票 > 编程 > 正文

表示操作的次数w,表示操作的次数w

输入输出样例

输入样例#1:

54x 3 8y 1 3x 4 9y 3 4

输出样例#1:

817

裸的线段树!

  1 #include<iostream>  2 #include<cstdio>  3 #include<cstring>  4 #include<cmath>  5 #include<queue>  6 #include<algorithm>  7 #define ls k<<1  8 #define rs k<<1|1  9 using namespace std; 10 const int MAXN=100001; 11 void read(int &n) 12 { 13     char c='+';int x=0;bool flag=0; 14     while(c<'0'||c>'9') 15     {c=getchar();if(c=='-')flag=1;} 16     while(c>='0'&&c<='9') 17     {x=x*10+c-48,c=getchar();} 18     flag==1?n=-x:n=x; 19 } 20 int n,m,chair; 21 int ans=-1; 22 int now=0; 23 int you,mei; 24 struct node 25 { 26     int l,r,w,fm; 27 }tree[MAXN*4]; 28 void update(int k) 29 { 30     tree[k].w=tree[ls].w+tree[rs].w; 31 } 32 void pushdown(int k) 33 { 34     tree[ls].w+=(tree[ls].r-tree[ls].l+1)*tree[k].fm; 35     tree[rs].w+=(tree[rs].r-tree[rs].l+1)*tree[k].fm; 36     tree[ls].fm+=tree[k].fm; 37     tree[rs].fm+=tree[k].fm; 38     tree[k].fm=0; 39     //cout<<"ls:"<<<<" "<<tree[ls].w<<" "; 40     //cout<<"rs:"<<<<" "<<tree[rs].w<<" "<<endl; 41 } 42 void build_tree(int ll,int rr,int k) 43 { 44     tree[k].l=ll;tree[k].r=rr; 45     if(ll==rr) 46     { 47         tree[k].w=0; 48         return ; 49     } 50     int mid=>>1; 51     build_tree(ll,mid,ls); 52     build_tree(mid+1,rr,rs); 53     update; 54 } 55 void interval_ask(int ll,int rr,int k) 56 { 57     if(ll>tree[k].r||rr<tree[k].l) 58         return ; 59     if(ll<=tree[k].l&&tree[k].r<=rr) 60     { 61         ans+=tree[k].w; 62         return ; 63     } 64     int mid=(tree[k].l+tree[k].r)>>1; 65     if(tree[k].fm) 66     pushdown; 67     if(ll<=mid) 68     interval_ask; 69     if(rr>mid) 70     interval_ask; 71     if(tree[k].fm) 72     pushdown; 73 } 74 void point_change(int pos,int v,int k) 75 { 76     if(pos>tree[k].r||pos<tree[k].l) 77         return ; 78     if(tree[k].l==tree[k].r) 79     { 80         tree[k].w+=v; 81         return ; 82     } 83     point_change; 84     point_change; 85     update; 86 } 87 void interval_change(int ll,int rr,int num,int k) 88 { 89     if(ll>tree[k].r||rr<tree[k].l) 90         return ; 91     if(ll<=tree[k].l&&rr>=tree[k].r) 92     { 93         tree[k].w+=num; 94         tree[k].fm+=(tree[k].r-tree[k].l+1)*num; 95         return ; 96     } 97     int mid=(tree[k].l+tree[k].r)>>1; 98     if(tree[k].fm) 99     pushdown;100     if(ll<=mid)101     interval_change(ll,rr,num,ls);102     if(rr>mid)103     interval_change(ll,rr,num,rs);104     update;105 }106 int main()107 {108     read;read;109     build_tree(1,n,1);110     for(int i=1;i<=m;i++)111     {112         char how;113         cin>>how;114         if(how=='x')115         {116             int pos,v;117             read;read;118             point_change(pos,v,1);119         }120         else 121         {122             ans=0;123             int x,y;124             read;read;125             interval_ask(x,y,1);126             printf("%dn",ans);127         }128     }129     return 0;130 } 

澳门三合彩票,题目描述

给定一个长度为n(n<=100000),初始值都为0的序列,x(x<=10000)次的修改某些位置上的数字,每次加上一个数,然后提出y (y<=10000)个问题,求每段区间的和。时间限制1秒。

输入输出格式

输入格式:

第一行1个数,表示序列的长度n

第二行1个数,表示操作的次数w

后面依次是w行,分别表示加入和询问操作

其中,加入用x表示,询问用y表示

x的格式为"x a b" 表示在序列a的位置加上b

y的格式为"y a b" 表示询问a到b区间的加和

输出格式:

每行一个数,分别是每次询问的结果

P2068 统计和,P2068统计

本文由澳门三合彩票发布于编程,转载请注明出处:表示操作的次数w,表示操作的次数w

关键词: