青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

ArcTan

dfs
隨筆 - 16, 文章 - 117, 評(píng)論 - 6, 引用 - 0
數(shù)據(jù)加載中……

poj 3468 線段樹

http://poj.org/problem?id=3468

線段數(shù)的構(gòu)造,查詢,修改!
struct node{
   int l,r,m;
   long long sum;//當(dāng)前區(qū)間的和
   long long add;//區(qū)間需要加上的數(shù)值
}

題意:
      給定n個(gè)數(shù)字A1,A2,..,An,Q個(gè)操作。
      C x y z,把區(qū)間x y內(nèi)的數(shù)都加上z
      Q x y,求區(qū)間x y內(nèi)所有數(shù)的和。
總結(jié):
      基礎(chǔ)代碼一定要對(duì),調(diào)試了半天,最后發(fā)現(xiàn)是swap(x,y,t)寫錯(cuò)了!!!!
      WA了一次,數(shù)據(jù)是long long才行,要分析清楚數(shù)據(jù)范圍!!!

#include <cstdio>
#include 
<cstdlib>
#include 
<cstring>
#include 
<cmath>
#include 
<ctime>
#include 
<cassert>
#include 
<iostream>
#include 
<sstream>
#include 
<fstream>
#include 
<map>
#include 
<set>
#include 
<vector>
#include 
<queue>
#include 
<algorithm>
#define min(x,y) (x<y?x:y)
#define max(x,y) (x>y?x:y)
#define swap(x,y,t) (t=x,x=y,y=t)
#define clr(list) memset(list,0,sizeof(list))
#define LL long long
#define maxn 200005
using namespace std;
struct node{
    
int l,r,m;
    LL sum;
    LL add;
} tree[
2*maxn];
int a[maxn];
LL build(
int l,int r,int root)
{
    tree[root].l
=l;
    tree[root].r
=r;
    tree[root].m
=(l+r)/2;
    tree[root].add
=0;
    
if (l==r)
    {
        tree[root].sum
=a[l];
        
return tree[root].sum;
    }
    
long long sum_l=build(l,(l+r)/2,root*2);
    
long long sum_r=build((l+r)/2+1,r,root*2+1);
    tree[root].sum
=sum_l+sum_r;
    
return tree[root].sum;
}
int insert(int l,int r,int add,int root)
{
    
if (l<=tree[root].l && r>=tree[root].r)
    {
        tree[root].add
+=add;
        tree[root].sum
+=add * (tree[root].r-tree[root].l+1);
        
return 0;
    }
    
if (tree[root].add) //向下更新
    {
        tree[
2*root].sum+=tree[root].add * (tree[root*2].r-tree[root*2].l+1);
        tree[
2*root].add+=tree[root].add;
        tree[
2*root+1].sum+=tree[root].add * (tree[root*2+1].r-tree[root*2+1].l+1);
        tree[
2*root+1].add+=tree[root].add;
        tree[root].add
=0;
    }
    
if (l<=tree[root].m)
        insert(l,r,add,root
*2);
    
if (r>tree[root].m)
        insert(l,r,add,root
*2+1);
    tree[root].sum
=tree[root*2].sum+tree[root*2+1].sum;   //這里回溯啊
    return 0;
}
LL search(
int l,int r,int root)
{
    
if (l<=tree[root].l && r>=tree[root].r)
        
return tree[root].sum;
    
if (tree[root].add)  //向下更新
    {
        tree[
2*root].sum+=tree[root].add * (tree[root*2].r-tree[root*2].l+1);
        tree[
2*root].add+=tree[root].add;
        tree[
2*root+1].sum+=tree[root].add * (tree[root*2+1].r-tree[root*2+1].l+1);
        tree[
2*root+1].add+=tree[root].add;
        tree[root].add
=0;
    }
    LL sum_l
=0,sum_r=0;
    
if (l<=tree[root].m)
        sum_l
=search(l,r,2*root);
    
if (r>tree[root].m)
        sum_r
=search(l,r,2*root+1);
    
return sum_l+sum_r;
}
int main()
{
    
int n,m;
    
int x,y,z;
    
int tmp;
    
char ch;
    scanf(
"%d%d",&n,&m);
    
for (int i=1;i<=n;i++)
        scanf(
"%d",&a[i]);
    build(
1,n,1);

    
for (int i=1;i<=m;i++)
    {
        scanf(
"\n%c",&ch);
        
if (ch=='C')
        {
            scanf(
"%d%d%d",&x,&y,&z);
            
if (x>y)
                swap(x,y,tmp);
            insert(x,y,z,
1);
        }
        
else
        {
            scanf(
"%d%d",&x,&y);
            
if (x>y)
                swap(x,y,tmp);
            printf(
"%I64d\n",search(x,y,1));
        }
    }
    
return 0;
}


posted on 2012-07-25 10:54 wangs 閱讀(419) 評(píng)論(0)  編輯 收藏 引用 所屬分類: ACM-數(shù)據(jù)結(jié)構(gòu)

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            国产精品欧美风情| 亚洲国产精品成人久久综合一区 | 欧美激情国产日韩精品一区18| 激情丁香综合| 久久综合伊人77777蜜臀| 久久免费精品视频| 日韩视频国产视频| 一本色道久久综合亚洲二区三区| 欧美日韩一区二区在线播放| 亚洲男人的天堂在线观看| 香蕉久久夜色精品国产| 在线观看不卡| 一区二区欧美在线观看| 国产一区二区三区在线观看网站| 男人的天堂成人在线| 欧美日韩1区| 久久久国产精品亚洲一区 | 欧美日韩国产色站一区二区三区| 午夜精品成人在线视频| 久久九九精品| 亚洲一区免费| 久久蜜臀精品av| 亚洲在线一区| 免费久久久一本精品久久区| 亚洲中午字幕| 麻豆av一区二区三区久久| 一区二区三区国产在线| 久久精品国产亚洲一区二区| 亚洲视频香蕉人妖| 久久综合网络一区二区| 香蕉久久一区二区不卡无毒影院 | 日韩一二三区视频| 久久国产精品一区二区三区四区| 日韩视频一区二区三区在线播放| 欧美伊人久久久久久午夜久久久久| 亚洲精品国产品国语在线app| 亚洲欧美偷拍卡通变态| av不卡免费看| 欧美xxxx在线观看| 久久国产免费看| 欧美日韩性视频在线| 美女视频黄a大片欧美| 国产精品丝袜xxxxxxx| 亚洲精品资源美女情侣酒店| 极品少妇一区二区| 性欧美长视频| 性欧美暴力猛交69hd| 欧美日韩激情网| 亚洲大胆人体在线| 在线看不卡av| 久久人人爽人人| 久久亚洲综合色| 国产亚洲精品福利| 欧美在线视频一区二区三区| 欧美一区二区三区四区高清| 国产精品magnet| 亚洲美女视频网| 一区二区三区色| 欧美日韩八区| 亚洲韩国日本中文字幕| 亚洲日本一区二区| 欧美国产一区在线| 亚洲欧洲日夜超级视频| 亚洲欧洲日本专区| 欧美高清在线精品一区| 亚洲丰满在线| 99日韩精品| 欧美日韩另类丝袜其他| 一区二区三区四区五区精品| 亚洲午夜久久久久久尤物 | 嫩草影视亚洲| 亚洲欧洲精品天堂一级| 99v久久综合狠狠综合久久| 欧美精品www在线观看| 亚洲精品一区二区三区福利| 亚洲一区二区三区乱码aⅴ| 国产精品福利久久久| 亚洲图片欧洲图片av| 午夜亚洲视频| 国内外成人免费激情在线视频| 久久国产精品免费一区| 亚洲电影自拍| 亚洲色无码播放| 国产欧美欧美| 美女主播一区| 中日韩美女免费视频网址在线观看| 欧美怡红院视频| 在线观看日韩精品| 欧美激情小视频| 亚洲欧美久久久久一区二区三区| 久热国产精品| 宅男噜噜噜66国产日韩在线观看| 国产精品色网| 久久理论片午夜琪琪电影网| 亚洲精品乱码久久久久久久久| 午夜精品久久久久久久| 亚洲国产欧美在线| 国产精品久久亚洲7777| 亚洲一区二区三区中文字幕在线| 久久久久久色| 亚洲一区视频在线| 1024亚洲| 国产精品欧美一区喷水| 久久免费视频在线| 亚洲欧美日韩精品| 亚洲精品免费一区二区三区| 午夜久久资源| 99成人在线| 在线观看91精品国产入口| 国产精品视频你懂的| 欧美粗暴jizz性欧美20| 欧美亚洲视频在线观看| 亚洲国产专区| 久久久久网址| 亚洲在线日韩| av成人手机在线| 亚洲国产91色在线| 国产亚洲电影| 国产免费成人av| 国产精品jizz在线观看美国| 欧美mv日韩mv国产网站app| 亚久久调教视频| 正在播放日韩| 日韩午夜在线| 亚洲欧洲日产国码二区| 玖玖玖免费嫩草在线影院一区| 亚洲私人影院在线观看| 亚洲国产成人精品女人久久久| 国产在线播精品第三| 国产精品一区二区在线观看网站 | 国产精品久久一卡二卡| 欧美日韩妖精视频| 欧美日韩精品免费看 | 亚洲精品免费在线| 亚洲福利精品| 亚洲国产精品久久久久久女王| 久久综合伊人77777蜜臀| 久久精品国产成人| 久久gogo国模裸体人体| 欧美一区二区三区男人的天堂| 午夜精品久久久久久久| 午夜国产精品视频免费体验区| 亚洲视频 欧洲视频| 一区二区日韩欧美| 亚洲视频一区二区| 欧美一区二区三区免费观看| 久久精彩免费视频| 噜噜噜躁狠狠躁狠狠精品视频 | 精品99视频| 亚洲国产成人久久| 日韩视频中文字幕| 99re热这里只有精品免费视频| 日韩午夜av在线| 在线午夜精品自拍| 亚洲自拍偷拍一区| 欧美一区网站| 免费观看亚洲视频大全| 亚洲国产视频a| 夜夜嗨网站十八久久| 亚洲一区二区网站| 久久精品一区二区国产| 男女视频一区二区| 欧美日韩精品二区第二页| 欧美日韩精品在线观看| 国产精品一区三区| 狠狠综合久久av一区二区小说| 亚洲国产精品一区制服丝袜| 亚洲最新色图| 久久精品国产综合精品| 欧美国产综合一区二区| 亚洲第一中文字幕| 亚洲一区在线直播| 免费亚洲电影在线| 欧美日韩在线观看视频| 激情成人综合| 亚洲伊人久久综合| 卡通动漫国产精品| 亚洲色诱最新| 免费一级欧美片在线播放| 国产精品呻吟| 亚洲精品中文字幕在线观看| 欧美一级免费视频| 欧美国产综合| 午夜精品一区二区三区在线播放| 欧美gay视频| 国产一区二区三区黄| 99综合在线| 麻豆精品网站| 午夜亚洲视频| 欧美午夜在线视频| 亚洲国产日韩在线| 久久精品一区中文字幕| 在线天堂一区av电影| 美国十次了思思久久精品导航| 国产精品一区亚洲| 亚洲一区二区三区四区五区黄| 欧美高清在线一区二区| 午夜精品视频| 国产精品草草| 一区二区三区四区国产精品|