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

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>
            国产精品一区在线观看| 国产精品每日更新在线播放网址| 极品日韩久久| 欧美sm视频| 欧美人与禽性xxxxx杂性| 宅男噜噜噜66一区二区| 亚洲午夜91| 激情丁香综合| 亚洲伦理在线免费看| 国产精品草草| 嫩草影视亚洲| 国产精品成人免费精品自在线观看 | 欧美电影在线| 欧美日韩一区在线| 久久久久久久久久看片| 欧美激情一区二区三区在线视频| 一区二区三区久久精品| 午夜一区二区三区不卡视频| 亚洲高清久久| 亚洲在线不卡| 亚洲看片网站| 久久av二区| 亚洲永久在线| 免费在线一区二区| 久久久国产一区二区| 欧美全黄视频| 欧美成熟视频| 国产在线成人| 在线一区视频| 日韩一级欧洲| 久热精品在线视频| 欧美在线一二三四区| 欧美久久视频| 亚洲电影第1页| 国产亚洲激情| 亚洲一区二区在| 99成人在线| 欧美插天视频在线播放| 久久综合九色| 国产免费观看久久| 一本大道av伊人久久综合| 樱花yy私人影院亚洲| 欧美一区二区三区在线| 亚洲欧美视频一区二区三区| 欧美日本韩国一区| 亚洲国产99精品国自产| 亚洲大胆视频| 老司机午夜精品视频在线观看| 久久成人免费电影| 国产精品爽爽ⅴa在线观看| 日韩午夜av在线| 99re66热这里只有精品3直播| 久久综合一区| 欧美成人午夜免费视在线看片| 国产在线播放一区二区三区| 亚洲欧美综合精品久久成人| 午夜精品久久久久久99热软件| 欧美日韩日本视频| 亚洲乱码国产乱码精品精可以看 | 黄色成人在线| 久久激情久久| 久久九九有精品国产23| 国产女主播一区| 午夜免费日韩视频| 久久久久久91香蕉国产| 伊人久久噜噜噜躁狠狠躁| 久久精品夜色噜噜亚洲a∨| 久久人人爽国产| 亚洲福利免费| 欧美片第1页综合| 一本色道久久综合| 欧美一区二粉嫩精品国产一线天| 国产精品视屏| 久久久久九九视频| 欧美激情91| 亚洲午夜精品一区二区| 国产老肥熟一区二区三区| 午夜宅男久久久| 欧美aⅴ一区二区三区视频| 亚洲电影免费在线| 欧美美女日韩| 亚洲影院在线观看| 久久久久综合一区二区三区| 亚洲高清三级视频| 欧美日韩国产欧| 亚洲欧美日韩精品综合在线观看| 久久精品国产999大香线蕉| 狠狠色丁香久久婷婷综合丁香| 欧美成年人视频网站| 亚洲一区二区成人| 欧美成人精品影院| 亚洲一级黄色片| 伊人婷婷久久| 国产精品久久久爽爽爽麻豆色哟哟| 欧美亚洲三级| 日韩天堂在线观看| 久久深夜福利| 亚洲一区欧美一区| 在线观看欧美亚洲| 国产精品美女久久久久久久| 久久精品综合一区| 一区二区激情视频| 欧美va亚洲va香蕉在线| 亚洲欧美精品| 亚洲美女免费视频| 国产在线观看91精品一区| 欧美日韩国产区| 久久日韩粉嫩一区二区三区| 亚洲视频综合| 亚洲精品视频在线观看网站| 久久躁日日躁aaaaxxxx| 亚洲综合电影| 一区二区三区产品免费精品久久75| 国产永久精品大片wwwapp| 欧美日韩一区高清| 欧美精品一区二区三区在线播放 | 亚洲三级影院| 久久亚洲精选| 久久精品官网| 香蕉免费一区二区三区在线观看 | 日韩午夜视频在线观看| 在线精品高清中文字幕| 国产一区二区三区日韩欧美| 欧美三级午夜理伦三级中文幕| 欧美成人综合一区| 麻豆成人综合网| 久久久噜噜噜久久人人看| 午夜激情亚洲| 亚洲欧美偷拍卡通变态| 亚洲一区二区精品| 在线视频精品| 亚洲午夜免费视频| 亚洲一区二区高清视频| 一区二区三区欧美激情| 一区电影在线观看| 一本大道久久a久久综合婷婷 | 亚洲欧洲99久久| 亚洲一区二区四区| 亚洲一本视频| 午夜精品久久久久久久蜜桃app| 亚洲一区在线视频| 欧美制服丝袜第一页| 久久爱www.| 久久野战av| 欧美激情一区在线观看| 欧美区国产区| 欧美三级视频在线观看| 国产精品女人久久久久久| 国产精品综合| 激情婷婷欧美| 亚洲精品久久久久久久久久久久 | 亚洲一区国产一区| 美女视频黄a大片欧美| 久久精品成人| 欧美激情导航| 欧美午夜精品久久久久免费视| 国产精品久久久久久超碰 | 国内精品久久久久久久影视蜜臀| 狠狠色丁香久久综合频道| 亚洲国产精品第一区二区| 99在线精品免费视频九九视| 亚洲午夜电影| 久久久久国产精品麻豆ai换脸| 欧美xx视频| 日韩一级视频免费观看在线| 亚洲欧美日韩国产综合在线 | 欧美在线综合| 欧美精品免费看| 国产精品看片资源| 樱桃成人精品视频在线播放| 一区二区三区国产精品| 久久电影一区| 亚洲三级免费电影| 欧美一区二区在线免费播放| 欧美高清视频免费观看| 国产精品美女久久久久久2018 | 久久精品72免费观看| 亚洲二区在线| 午夜久久福利| 欧美日一区二区三区在线观看国产免 | 先锋影音网一区二区| 免费看黄裸体一级大秀欧美| 国产精品看片资源| 亚洲精品国产精品国自产观看浪潮| 亚洲在线观看视频| 亚洲国产第一页| 欧美在线不卡| 国产精品国产三级国产普通话99 | 久久综合给合| 亚洲欧美激情一区二区| 欧美区亚洲区| 亚洲国产高清视频| 久久成人在线| 中文高清一区| 欧美女同在线视频| 在线免费观看一区二区三区| 午夜欧美大尺度福利影院在线看| 亚洲国产一区二区三区高清 | 亚洲主播在线观看| 欧美日韩国产va另类|