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

ACM___________________________

______________白白の屋
posts - 182, comments - 102, trackbacks - 0, articles - 0
<2010年8月>
25262728293031
1234567
891011121314
15161718192021
22232425262728
2930311234

常用鏈接

留言簿(24)

隨筆分類(332)

隨筆檔案(182)

FRIENDS

搜索

積分與排名

最新隨筆

最新評論

閱讀排行榜

評論排行榜

MiYu原創, 轉帖請注明 : 轉載自 ______________白白の屋    

 

 

 

題目地址 :

      http://acm.hdu.edu.cn/showproblem.php?pid=1698

題目描述 : 

Just a Hook

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3841    Accepted Submission(s): 1675


Problem Description
In the game of DotA, Pudge’s meat hook is actually the most horrible thing for most of the heroes. The hook is made up of several consecutive metallic sticks which are of the same length.



Now Pudge wants to do some operations on the hook.

Let us number the consecutive metallic sticks of the hook from 1 to N. For each operation, Pudge can change the consecutive metallic sticks, numbered from X to Y, into cupreous sticks, silver sticks or golden sticks.
The total value of the hook is calculated as the sum of values of N metallic sticks. More precisely, the value for each kind of stick is calculated as follows:

For each cupreous stick, the value is 1.
For each silver stick, the value is 2.
For each golden stick, the value is 3.

Pudge wants to know the total value of the hook after performing the operations.
You may consider the original hook is made up of cupreous sticks.
 

Input
The input consists of several test cases. The first line of the input is the number of the cases. There are no more than 10 cases.
For each case, the first line contains an integer N, 1<=N<=100,000, which is the number of the sticks of Pudge’s meat hook and the second line contains an integer Q, 0<=Q<=100,000, which is the number of the operations.
Next Q lines, each line contains three integers X, Y, 1<=X<=Y<=N, Z, 1<=Z<=3, which defines an operation: change the sticks numbered from X to Y into the metal kind Z, where Z=1 represents the cupreous kind, Z=2 represents the silver kind and Z=3 represents the golden kind.
 

Output
For each case, print a number in a line representing the total value of the hook after the operations. Use the format in the example.
 

Sample Input
1 10 2 1 5 2 5 9 3
 

Sample Output
Case 1: The total value of the hook is 24.
 

 

標準的線段樹,  成段更新 ,......     具體看 代碼 注釋 .

 

代碼如下 :

 /*

Coded By  : MiYu

Link      : http://www.cnblogs.com/MiYu  || http://m.shnenglu.com/MiYu

Author By : MiYu

Test      : 1

Program   : 1698

*/

//#pragma warning( disable:4789 )

#include <iostream>

#include <algorithm>

#include <string>

#include <set>

#include <map>

#include <utility>

#include <queue>

#include <stack>

#include <list>

#include <vector>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

using namespace std;


typedef struct seg_tree{

int left, right, col;

bool cov; //標記當前線段是否被覆蓋, 如果true, 表示這一段線段的值都為 col. false則相反

int mid (){ return (left + right) >> 1; }

}SEG;

SEG seg[300010];

void creat ( int beg, int end, int rt = 1 ){

seg[rt].left = beg;

seg[rt].right = end;

seg[rt].col =  1;

seg[rt].cov =  true;

if ( beg == end ) return;

int mid = seg[rt].mid();

creat ( beg, mid, rt << 1 );

creat ( mid + 1, end, ( rt << 1 ) + 1 );

}

void modify ( int beg, int end, int val, int rt = 1 ){

int LL = rt << 1;

int RR = ( rt << 1 ) + 1;

if ( seg[rt].left == beg && seg[rt].right == end ){ //線段被覆蓋, 標記 cov 為true  

seg[rt].cov = true;

seg[rt].col = val;

return ;

}

if ( seg[rt].cov ){ //如果線段曾經被覆蓋,  標記 false, 將col往下傳  

seg[rt].cov = false;

seg[LL].col = seg[RR].col = seg[rt].col;

seg[LL].cov = seg[RR].cov = true;

}

int mid = seg[rt].mid();

if ( end <= mid ){

modify ( beg, end, val, LL );

} else if ( beg > mid ) {

modify ( beg, end, val, RR );

} else {

modify ( beg, mid, val, LL );

modify ( mid + 1, end, val, RR );

}

}

int quy ( int beg, int end, int rt = 1 ){

if ( seg[rt].cov ){  // 線段如果是被覆蓋的 , 直接返回這一段區間的值

return ( seg[rt].right - seg[rt].left + 1 ) * seg[rt].col;

}

int mid = seg[rt].mid();

return quy ( beg, mid, rt << 1 ) + quy ( mid + 1, end, ( rt << 1 ) + 1 );

}


int main ()

{

int T, ca = 1;

scanf ( "%d", &T );

while ( T -- ){

int N;

scanf ( "%d", &N );

creat ( 1, N );

int M;

scanf ( "%d", &M );

for ( int i = 1; i <= M; ++ i ){

int beg, end, val;

scanf ( "%d%d%d", &beg, &end, &val );

modify ( beg, end, val );

}

printf ( "Case %d: The total value of the hook is %d.\n", ca++,quy( 1, N ) );

}

    return 0;

}


/*

1

10

2

1 5 2

5 9 3

*/



/*    此為一牛人代碼 , 速度 非常快 !!!! 0rz.........

#include<stdio.h>

int a[100001][3],c[100001];

int main()

{

    int t,i,j,n,m,sum,v,w=1;

    scanf("%d",&t);

    while(t--&&scanf("%d %d",&n,&m))

    {

        sum=0;

        for(i=1;i<=m;i++)

        scanf("%d %d %d",&a[i][0],&a[i][1],&a[i][2]);

        for(i=1;i<=n;i++)

        {

            v=1;

            for(j=m;j>=1;j--)

            {

                if(a[j][0]<=i&&a[j][1]>=i)

                {

                    v=a[j][2];

                    break;

                }

            }

            sum+=v;

        }

        printf("Case %d: The total value of the hook is %d.\n",w++,sum);

    }

}



*/

 

Feedback

# re: HDOJ 1698 HDU 1698 Just a Hook ACM 1698 IN HDU[未登錄]  回復  更多評論   

2010-09-18 11:18 by bb
下面的代碼只是剛好數據不能卡把?復雜度O(n*m)~

# re: HDOJ 1698 HDU 1698 Just a Hook ACM 1698 IN HDU  回復  更多評論   

2010-09-18 11:42 by MiYu
Accepted 1698 437MS 4300K 2117 B C++
這是 線段樹 的 AC 判定,
Accepted 1698 218MS 1360K 630 B C++
這是后面方法的 AC 判定, 快了 一倍

# re: HDOJ 1698 HDU 1698 Just a Hook ACM 1698 IN HDU[未登錄]  回復  更多評論   

2010-09-18 17:39 by bb
不是呀,只是OJ數據沒卡到這方法~~

# re: HDOJ 1698 HDU 1698 Just a Hook ACM 1698 IN HDU  回復  更多評論   

2010-10-30 07:56 by MiYu
我覺得 哪方法 很牛B =. =
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            国产欧美精品一区| 国产欧美一区二区精品秋霞影院 | 欧美一区二区三区四区高清| 国产精品日产欧美久久久久| 久久国内精品视频| 欧美专区第一页| 亚洲欧洲日产国产网站| 亚洲日本理论电影| 国产精品美女黄网| 久久久久www| 欧美成人精品激情在线观看| 一区二区精品| 欧美一区二区高清| 亚洲激情网址| 亚洲先锋成人| 亚洲成色777777在线观看影院| 亚洲成人资源| 国产精品亚洲а∨天堂免在线| 久久影视三级福利片| 欧美久久九九| 久久久久国色av免费观看性色| 欧美电影打屁股sp| 欧美一区二区三区久久精品茉莉花 | 欧美激情一二区| 国产精品久久国产愉拍| 免费成人高清视频| 国产精品久久久久久久久婷婷| 久久女同互慰一区二区三区| 欧美日韩国产免费| 久久综合九色综合网站| 欧美日韩免费观看一区| 鲁鲁狠狠狠7777一区二区| 欧美午夜精品理论片a级大开眼界 欧美午夜精品理论片a级按摩 | 蜜臀久久99精品久久久久久9 | 欧美性猛片xxxx免费看久爱| 玖玖玖免费嫩草在线影院一区| 欧美三级网址| 欧美高清成人| 国内成+人亚洲| 一区二区三区欧美成人| 亚洲精品久久久久久久久久久| 亚洲自拍偷拍福利| 在线亚洲激情| 欧美第十八页| 欧美激情视频一区二区三区免费| 国产区欧美区日韩区| 9人人澡人人爽人人精品| 亚洲精品日本| 久久亚洲一区| 久久亚洲二区| 国内成+人亚洲| 亚洲欧美伊人| 欧美在线高清| 国产九色精品成人porny| 日韩一级裸体免费视频| 亚洲伦理精品| 欧美激情第8页| 欧美成人在线免费视频| 在线播放日韩欧美| 久久婷婷麻豆| 亚洲福利在线看| 亚洲精品少妇30p| 欧美激情一二三区| 亚洲欧洲日产国产网站| 日韩视频一区二区三区在线播放免费观看| 久久久久成人网| 美腿丝袜亚洲色图| 亚洲国产精品一区二区久 | 亚洲人成久久| 一区二区日韩免费看| 欧美在线观看一二区| 国产精品久久97| 亚洲欧美国内爽妇网| 久久精品91| 在线观看av一区| 免费观看在线综合| 亚洲免费av片| 午夜久久一区| 国产亚洲亚洲| 欧美1区2区视频| 一区二区成人精品| 欧美专区福利在线| 亚洲成人在线网| 欧美日韩国产999| 亚洲一区www| 久久久久久噜噜噜久久久精品| 在线观看日韩av先锋影音电影院| 蜜臀av国产精品久久久久| 亚洲美洲欧洲综合国产一区| 欧美一级理论性理论a| 国语自产精品视频在线看抢先版结局| 久久午夜影视| 中国成人在线视频| 久久精品亚洲乱码伦伦中文 | 欧美另类一区| 亚洲欧美综合v| 亚洲高清一区二| 欧美一区二区三区免费视频| 亚洲国产精品第一区二区| 欧美激情1区| 久久av一区二区三区漫画| 亚洲激情电影在线| 久久久久久久性| 亚洲天堂成人在线视频| 精品成人在线| 国产精品99免费看| 美女尤物久久精品| 午夜精品久久久久久久99樱桃 | 久久精品青青大伊人av| 亚洲精品一区二区三区99| 久久精品国产精品 | 国产日韩亚洲| 欧美精品一线| 免费高清在线一区| 欧美亚洲一区二区在线| 99精品国产在热久久下载| 毛片一区二区三区| 久久xxxx| 亚洲欧美高清| 一本色道久久综合亚洲精品不卡 | 午夜精品福利视频| 亚洲最新合集| 亚洲黄色有码视频| 国内精品久久久久伊人av| 欧美午夜剧场| 欧美日韩国产精品一区| 麻豆精品精品国产自在97香蕉| 欧美一区二区免费| 亚洲欧美日本视频在线观看| av成人黄色| 99精品热6080yy久久| 91久久国产综合久久91精品网站| 欧美jizz19hd性欧美| 久久免费精品日本久久中文字幕| 欧美一区二区精品在线| 午夜激情一区| 香蕉久久国产| 美女在线一区二区| 久久视频这里只有精品| 久久精品男女| 久久久亚洲国产天美传媒修理工| 久久精品日产第一区二区三区| 性欧美精品高清| 欧美一区二区播放| 久久国产一二区| 久久久久网址| 免费人成精品欧美精品| 欧美国产亚洲精品久久久8v| 欧美成人自拍| 国产精品成人免费视频| 国产精品久在线观看| 国产情人综合久久777777| 国产日韩亚洲欧美综合| 国内精品模特av私拍在线观看| 狠狠色丁香久久综合频道| 在线观看欧美日韩国产| 亚洲人在线视频| 亚洲午夜精品福利| 欧美一区二区三区久久精品茉莉花| 性视频1819p久久| 久久综合久久综合这里只有精品| 免费观看国产成人| 亚洲精品国产精品国自产观看| 亚洲美女网站| 亚洲直播在线一区| 久久久久一本一区二区青青蜜月| 欧美刺激性大交免费视频| 国产精品xvideos88| 国产一区二区三区日韩欧美| 亚洲国产另类久久久精品极度| 日韩视频精品在线观看| 欧美伊人久久久久久久久影院| 久久中文字幕一区| 亚洲精品乱码| 久久国产精品久久精品国产| 欧美精品免费视频| 国产欧美在线视频| 亚洲美女在线看| 久久高清免费观看| 亚洲精品国产精品乱码不99 | 另类成人小视频在线| 国产精品捆绑调教| 亚洲国产精品传媒在线观看| 亚洲欧美日韩综合一区| 欧美激情一二区| 欧美一区二区三区男人的天堂| 欧美黄色aaaa| 韩日欧美一区| 亚洲欧美色婷婷| 亚洲激情av在线| 久久精品国产综合| 国产精品扒开腿爽爽爽视频| 亚洲国产一区二区在线| 久久国产精品久久久| 一本到高清视频免费精品| 久久中文字幕一区二区三区| 国产日韩三区| 午夜电影亚洲| 一本久道久久综合婷婷鲸鱼 | 一区二区三区欧美日韩|