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

oyjpArt ACM/ICPC算法程序設(shè)計(jì)空間

// I am new in programming, welcome to my blog
I am oyjpart(alpc12, 四城)
posts - 224, comments - 694, trackbacks - 0, articles - 6
Minimizing maximizer
Time Limit: 5000MS Memory Limit: 30000K
Total Submissions: 1004 Accepted: 280

Description
The company Chris Ltd. is preparing a new sorting hardware called Maximizer. Maximizer has n inputs numbered from 1 to n. Each input represents one integer. Maximizer has one output which represents the maximum value present on Maximizer's inputs.

Maximizer is implemented as a pipeline of sorters Sorter(i1, j1), ... , Sorter(ik, jk). Each sorter has n inputs and n outputs. Sorter(i, j) sorts values on inputs i, i+1,... , j in non-decreasing order and lets the other inputs pass through unchanged. The n-th output of the last sorter is the output of the Maximizer.

An intern (a former ACM contestant) observed that some sorters could be excluded from the pipeline and Maximizer would still produce the correct result. What is the length of the shortest subsequence of the given sequence of sorters in the pipeline still producing correct results for all possible combinations of input values?

Task
Write a program that:

reads a description of a Maximizer, i.e. the initial sequence of sorters in the pipeline,
computes the length of the shortest subsequence of the initial sequence of sorters still producing correct results for all possible input data,
writes the result.

Input
The first line of the input contains two integers n and m (2 <= n <= 50000, 1 <= m <= 500000) separated by a single space. Integer n is the number of inputs and integer m is the number of sorters in the pipeline. The initial sequence of sorters is described in the next m lines. The k-th of these lines contains the parameters of the k-th sorter: two integers ik and jk (1 <= ik < jk <= n) separated by a single space.

Output
The output consists of only one line containing an integer equal to the length of the shortest subsequence of the initial sequence of sorters still producing correct results for all possible data.

Sample Input

40 6
20 30
1 10
10 20
20 30
15 25
30 40

 

Sample Output

4

 

Hint
Huge input data, scanf is recommended.

Source
Central Europe 2003

//pku1769
/*
 * trival DP dp[i] = dp[j] + 1 (if there is a segment starting from a->i && a <= j)  o(n^2)
 * 考慮到轉(zhuǎn)移的時(shí)候選擇的是一段內(nèi)的最小dp值,運(yùn)用點(diǎn)樹(shù)可以解決
 */
#include <string.h>
#include <stdio.h>

const int N = 50010;
const int MAXINT = 1000000000;

int n, l;

struct ST {int i,j,m,l,r,c;} st[2*N];
int up, cnt;

void bd(int d, int x, int y) {
 st[d].i = x, st[d].j = y, st[d].m = (x+y)/2, st[d].c = MAXINT;
 if(x < y) {
  st[d].l = ++up; bd(up, x, st[d].m);
  st[d].r = ++up; bd(up, st[d].m+1, y);
 }
}

void ins(int d, int x, int c) {
 if(c < st[d].c)
  st[d].c = c;
 if(st[d].i != st[d].j) {
  if(x <= st[d].m)
   ins(st[d].l, x, c);
  else
   ins(st[d].r, x, c);
 }
}

int getmin(int d, int x, int y) {
 if(x <= st[d].i && y >= st[d].j)
  return st[d].c;
 int min = MAXINT;
 if(x <= st[d].m) {
  int now = getmin(st[d].l, x, y);
  if(now < min) min = now;
 }
 if(y > st[d].m) {
  int now = getmin(st[d].r, x, y);
  if(now < min) min = now;
 }
 return min;
}

int main() {
 int i, a, b;
 up = 0;
 scanf("%d %d ", &l, &n);
 bd(0, 1, l);
 ins(0, 1, 0);
 int max = 0;
 for(i = 0; i < n; ++i) {
  scanf("%d%d", &a, &b);
  if(a < b) {
   int min = getmin(0, a, b-1);
   ins(0, b, min+1);
  }
 }
 printf("%d\n", getmin(0, l, l));
 return 0;
}

Feedback

# re: pku1769 新寫的線段樹(shù)(點(diǎn)樹(shù))模版  回復(fù)  更多評(píng)論   

2007-12-04 16:33 by je
題目沒(méi)看懂,能解釋下么?

# re: pku1769 新寫的線段樹(shù)(點(diǎn)樹(shù))模版  回復(fù)  更多評(píng)論   

2007-12-05 11:47 by oyjpart
給定一個(gè)線段集,要求選擇其中一個(gè)最小的子集來(lái)覆蓋整個(gè)區(qū)域。
要求選定的子集是按照題目給的序來(lái)覆蓋。

# re: pku1769 新寫的線段樹(shù)(點(diǎn)樹(shù))模版  回復(fù)  更多評(píng)論   

2008-01-18 08:46 by Littleye
很多測(cè)試好像得不到正確答案,例如:
40 4
10 30
14 29
25 30
30 40
答案應(yīng)該是2,你的程序給的是1000000000(你的初始值)
類似的例子還有不少

# re: pku1769 新寫的線段樹(shù)(點(diǎn)樹(shù))模版  回復(fù)  更多評(píng)論   

2008-01-18 12:40 by oyjpart
你的樣例是無(wú)解的,沒(méi)有線段覆蓋【0,10】的區(qū)間。

# re: pku1769 新寫的線段樹(shù)(點(diǎn)樹(shù))模版  回復(fù)  更多評(píng)論   

2008-01-19 02:33 by Littleye
I understand now. I don't think I understood the problem thoroughly before. Although the problem description doesn't clearly indicate that all the segments given should cover the whole segment(1,N), it is the right situation or else we can't get the right output from the maximizer. Now the problem description says that we can get the right output, so the subsequences given must cover the whole segments. Thanks a lot!

# re: pku1769 新寫的線段樹(shù)(點(diǎn)樹(shù))模版  回復(fù)  更多評(píng)論   

2008-01-19 12:34 by oyjpart
you are welcome

# re: pku1769 新寫的線段樹(shù)(點(diǎn)樹(shù))模版  回復(fù)  更多評(píng)論   

2008-04-18 10:44 by l-y-p
向大牛學(xué)習(xí)學(xué)習(xí),“運(yùn)用點(diǎn)樹(shù)可以解決”,好思想,很好很強(qiáng)大。但是還有一個(gè)疑點(diǎn):在DP的時(shí)候應(yīng)該從小到大進(jìn)行,但是沒(méi)發(fā)現(xiàn)你對(duì)y坐標(biāo)進(jìn)行排序就直接進(jìn)行,那如果是考慮這樣兩組數(shù)據(jù):
10 40
0 10
從10到40先確定到40的DP值為maxint+1,然后再由0~10確定10的值為1,這樣是不是有問(wèn)題??你的程序我沒(méi)調(diào)試過(guò),不曉得你是怎么處理的?

# re: pku1769 新寫的線段樹(shù)(點(diǎn)樹(shù))模版  回復(fù)  更多評(píng)論   

2008-04-18 10:58 by l-y-p
果然啊,剛調(diào)試了下,直接運(yùn)行數(shù)據(jù):
40 2
10 40
0 10
結(jié)果是1000000000,不知道是我沒(méi)看清楚還是程序的bug?

# re: pku1769 新寫的線段樹(shù)(點(diǎn)樹(shù))模版  回復(fù)  更多評(píng)論   

2008-04-18 12:19 by oyjpart
題目是有這樣的要求的:
要求選定的子集是按照題目給的序來(lái)覆蓋。
嘿嘿 如果我沒(méi)有理解錯(cuò)你的意思的話

# re: pku1769 新寫的線段樹(shù)(點(diǎn)樹(shù))模版  回復(fù)  更多評(píng)論   

2008-04-18 22:02 by l-y-p
汗!
What is the length of the shortest subsequence of the given sequence of sorters
把排序一去掉就AC了,多謝大牛指點(diǎn),呵呵。
最先還一直在想如果可以排序的話就用不著用點(diǎn)樹(shù)了,直接貪心!

# re: pku1769 新寫的線段樹(shù)(點(diǎn)樹(shù))模版  回復(fù)  更多評(píng)論   

2009-08-25 10:39 by demo
你的程序過(guò)不了zoj 2451

# re: pku1769 新寫的線段樹(shù)(點(diǎn)樹(shù))模版  回復(fù)  更多評(píng)論   

2009-09-07 23:58 by oyjpart
題目是一樣的嗎

# re: pku1769 新寫的線段樹(shù)(點(diǎn)樹(shù))模版  回復(fù)  更多評(píng)論   

2010-12-01 20:36 by LSK
請(qǐng)仔細(xì)讀題。。。ZJU哪個(gè)是multi case的
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            欧美日韩一区二| 久久米奇亚洲| 国产精品日韩一区| 午夜亚洲伦理| 久久福利电影| 亚洲激情二区| 亚洲美女av网站| 国产精品美女久久| 久久高清国产| 蜜桃精品一区二区三区| 99国产麻豆精品| 亚洲淫片在线视频| 国内精品免费在线观看| 欧美激情一区二区三级高清视频| 欧美日韩高清免费| 欧美一进一出视频| 欧美91视频| 亚洲欧美日韩国产成人精品影院| 欧美中文字幕视频在线观看| 亚洲区国产区| 亚洲天堂成人在线观看| 亚洲电影免费观看高清| 亚洲免费观看在线观看| 国内精品久久久久伊人av| 最近中文字幕日韩精品| 国产精品日韩二区| 欧美激情中文字幕一区二区| 欧美午夜片在线观看| 麻豆成人综合网| 欧美偷拍另类| 欧美激情亚洲| 国内外成人免费激情在线视频网站| 亚洲国产第一| 一区二区三区在线观看视频| 夜夜爽99久久国产综合精品女不卡| 国产夜色精品一区二区av| 亚洲精品欧美日韩专区| 在线成人免费视频| 午夜精品福利视频| 亚洲一区精品电影| 蜜桃视频一区| 久久久亚洲高清| 国产精品美女午夜av| 亚洲精品国产精品国自产观看| 国产亚洲亚洲| 一区二区高清视频| 99国内精品久久| 蜜臀久久99精品久久久久久9 | 国产精品视屏| 亚洲精品国产精品乱码不99| 亚洲成人在线免费| 欧美在线999| 久久av老司机精品网站导航| 国产精品久久亚洲7777| 日韩午夜精品视频| 一本一本久久a久久精品综合妖精| 久热精品在线| 免费观看成人网| 韩国av一区二区| 欧美一二三区精品| 久久久亚洲影院你懂的| 国内外成人免费激情在线视频| 亚洲欧美视频在线| 久久久91精品国产一区二区三区| 国产精品久久久久三级| 亚洲视频在线观看网站| 午夜精品影院在线观看| 国产精品一区视频| 欧美一区二区三区在线看 | 午夜宅男久久久| 国产农村妇女精品一区二区| 亚洲欧美日韩国产综合| 久久久国产精品一区二区三区| 国产亚洲二区| 久久精品视频导航| 欧美黄污视频| 一本久道久久综合婷婷鲸鱼| 欧美性大战xxxxx久久久| 亚洲一区999| 久久午夜羞羞影院免费观看| 亚洲国产高清在线| 欧美精品一区二区三区蜜臀 | 久久久亚洲精品一区二区三区| 国模叶桐国产精品一区| 免费毛片一区二区三区久久久| 亚洲第一成人在线| 亚洲一级黄色片| 国产一区二区欧美| 欧美国产日本韩| 亚洲视频播放| 欧美成人a∨高清免费观看| 日韩一区二区精品在线观看| 国产精品视频一区二区高潮| 久久美女性网| 一本久道久久综合中文字幕| 久久久精彩视频| 亚洲精选国产| 国产亚洲精品bt天堂精选| 欧美成人首页| 亚洲欧美日韩久久精品| 亚洲第一精品影视| 欧美一区成人| 日韩午夜黄色| 精品成人在线视频| 国产精品久久久久毛片软件| 久久精品一区中文字幕| 99国产精品久久久久老师| 久久久噜噜噜久久久| 这里只有精品视频在线| 影音先锋中文字幕一区| 国产精品免费电影| 欧美日本一道本在线视频| 久久精品欧美日韩精品| 亚洲视频视频在线| 亚洲精品社区| 欧美顶级少妇做爰| 久久久免费精品视频| 午夜精品久久久久久久| 日韩午夜激情av| 亚洲国产成人在线| 精品动漫3d一区二区三区免费版| 国产精品白丝黑袜喷水久久久| 欧美高清视频在线观看| 久久另类ts人妖一区二区| 亚洲在线免费| 国产精品99久久久久久久女警| 亚洲欧洲在线视频| 欧美福利视频在线观看| 久久免费黄色| 久久久国产精彩视频美女艺术照福利| 亚洲在线观看免费视频| 亚洲香蕉网站| 亚洲视频在线观看一区| 亚洲乱码久久| 日韩性生活视频| 日韩小视频在线观看| 亚洲狼人精品一区二区三区| 亚洲激情av| 亚洲区免费影片| 日韩视频国产视频| 一本色道久久88亚洲综合88| 日韩视频亚洲视频| 在线一区二区三区四区五区| 亚洲免费观看视频| 亚洲视频每日更新| 亚洲欧美另类国产| 久久精品免视看| 老牛影视一区二区三区| 老鸭窝毛片一区二区三区| 久久综合狠狠综合久久综合88 | 久久国产精品久久久久久久久久| 香蕉久久久久久久av网站| 午夜宅男久久久| 久久精品国语| 欧美激情偷拍| 一区二区三区黄色| 午夜精品久久久久久99热| 久久精品国产免费看久久精品| 久久九九热免费视频| 老色批av在线精品| 欧美精品一区二区在线播放| 欧美视频在线视频| 国产视频在线观看一区二区| 狠狠爱成人网| 亚洲精品欧美| 亚洲欧洲99久久| 免费日韩视频| 亚洲最新合集| 久久久xxx| 欧美日韩在线三级| 国产一区二区三区四区五区美女| 在线观看视频亚洲| 亚洲午夜一区二区三区| 久久免费精品视频| 99国产精品自拍| 久久精品免费看| 欧美网站在线观看| 亚洲福利视频一区二区| 亚洲午夜精品| 欧美jizz19hd性欧美| 国产精品99久久久久久久vr| 久久偷窥视频| 国产精品日韩精品欧美在线 | 国产日韩欧美另类| 亚洲精品一区中文| 久久精品国产欧美亚洲人人爽| 亚洲高清av在线| 性欧美暴力猛交另类hd| 欧美日韩大片| 亚洲国产精品成人精品| 欧美一区亚洲二区| 夜夜嗨av色一区二区不卡| 久久精品人人爽| 国产精品五区| 一区二区久久久久久| 欧美成年人视频| 久久xxxx精品视频| 国产麻豆精品久久一二三| 一本综合久久| 亚洲高清在线播放|