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

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>
            久久久人成影片一区二区三区观看| 亚洲黄网站黄| 亚洲婷婷免费| 国产精品免费小视频| 亚洲免费影视| 欧美一区二区三区播放老司机 | 一区二区三区四区五区在线| 欧美日韩免费观看一区三区| 亚洲免费影视第一页| 午夜亚洲伦理| 亚洲精品精选| 亚洲一区在线观看免费观看电影高清| 国产伦精品一区二区| 久热这里只精品99re8久| 欧美sm视频| 亚洲欧美国产va在线影院| 新67194成人永久网站| 亚洲大胆在线| 亚洲一区在线免费| 伊人久久男人天堂| 夜夜爽www精品| 国产一区二区三区无遮挡| 亚洲高清在线观看| 国产精品人人爽人人做我的可爱 | 日韩亚洲国产精品| 欧美午夜视频网站| 另类专区欧美制服同性| 欧美私人啪啪vps| 欧美亚洲一区二区在线| 久久久另类综合| 国产精品99久久久久久久vr| 欧美一区在线看| 9i看片成人免费高清| 亚洲视频欧美在线| 美女脱光内衣内裤视频久久影院| 亚洲午夜一区| 免费91麻豆精品国产自产在线观看| 亚洲尤物视频网| 欧美成人精品高清在线播放| 久久国产精品免费一区| 欧美日韩亚洲三区| 亚洲丁香婷深爱综合| 国产亚洲精品自拍| 一区二区日本视频| 亚洲作爱视频| 欧美成va人片在线观看| 久久综合999| 国产伦一区二区三区色一情| 亚洲激情校园春色| 亚洲国产91| 久久久.com| 久久国产精品久久精品国产| 欧美性做爰猛烈叫床潮| 亚洲日本电影在线| 亚洲日本欧美| 欧美激情精品久久久久久久变态| 久久久久9999亚洲精品| 国产麻豆综合| 亚洲欧美制服另类日韩| 欧美一区二区三区在线免费观看| 欧美日韩成人一区二区三区| 亚洲国产小视频在线观看| 亚洲人成在线观看| 欧美gay视频| 91久久久在线| 夜夜爽夜夜爽精品视频| 欧美日韩国产bt| 亚洲人www| 亚洲天堂av图片| 欧美午夜在线一二页| 一区二区成人精品| 午夜视频在线观看一区二区三区| 国产精品久久99| 亚洲欧美在线x视频| 久久久久国色av免费观看性色| 国产欧美日韩一级| 久久成人一区二区| 欧美成人综合一区| 亚洲免费播放| 国产精品每日更新| 欧美在线999| 亚洲第一在线综合在线| 日韩视频免费大全中文字幕| 欧美日韩免费观看一区二区三区 | 一区二区av在线| 欧美亚洲一区三区| 伊人久久综合97精品| 欧美va亚洲va香蕉在线| 亚洲作爱视频| 久久久成人精品| 亚洲国产小视频| 欧美日韩国产成人在线观看| 亚洲一区高清| 欧美成人午夜77777| 亚洲午夜精品久久久久久浪潮 | 国产区亚洲区欧美区| 久久婷婷亚洲| 在线亚洲成人| 免费试看一区| 亚洲男女毛片无遮挡| 精品动漫一区| 国产精品jvid在线观看蜜臀| 欧美一区二区日韩一区二区| 亚洲福利视频免费观看| 午夜一区二区三视频在线观看| 精品1区2区| 国产精品二区三区四区| 麻豆精品在线播放| 亚洲欧美另类国产| 亚洲精品日本| 免费成人激情视频| 久久爱另类一区二区小说| 日韩午夜av在线| 在线播放日韩专区| 国产精品美女视频网站| 欧美精品久久久久久| 欧美一区二区在线免费观看 | 久久视频在线看| 中国av一区| 亚洲日本欧美日韩高观看| 国内精品美女在线观看| 国产精品福利在线观看网址| 欧美大胆a视频| 久久九九免费视频| 亚洲欧美日韩久久精品| 一区二区三区www| 亚洲精品免费网站| 欧美激情中文字幕乱码免费| 久久久久久久欧美精品| 亚洲在线观看免费| 亚洲精品视频在线看| 亚洲福利视频在线| 一区精品久久| 极品尤物av久久免费看| 国产综合欧美| 国产在线拍偷自揄拍精品| 国产欧美日韩亚洲一区二区三区 | 欧美在线视频观看免费网站| 亚洲一区综合| 亚洲欧美国产一区二区三区| 亚洲五月婷婷| 亚洲欧美日韩第一区| 亚洲自拍啪啪| 香蕉久久国产| 欧美在现视频| 久久人人爽人人爽爽久久| 久久偷看各类wc女厕嘘嘘偷窃| 久久精品国产精品亚洲综合| 欧美在现视频| 久久视频精品在线| 免费观看成人www动漫视频| 欧美不卡高清| 欧美日韩一区二区免费在线观看| 欧美日韩视频专区在线播放 | 欧美剧在线免费观看网站| 欧美精品乱码久久久久久按摩 | 午夜精品理论片| 先锋a资源在线看亚洲| 久久se精品一区二区| 久久久精彩视频| 欧美高清不卡在线| 欧美视频在线观看一区二区| 国产精品美女久久久| 国产亚洲精品一区二555| 在线日韩视频| 亚洲无毛电影| 久久精品在这里| 亚洲电影毛片| 一本到12不卡视频在线dvd| 亚洲一区区二区| 久久久久综合网| 欧美日韩精品一区| 国产一区日韩一区| 亚洲美女视频在线观看| 欧美一区二区三区四区高清| 久热这里只精品99re8久| 亚洲欧洲中文日韩久久av乱码| 亚洲视频你懂的| 久久久精品免费视频| 欧美日韩国产一中文字不卡| 国产欧美 在线欧美| 91久久国产精品91久久性色| 亚洲一区二区免费看| 麻豆国产精品777777在线 | 看欧美日韩国产| 亚洲作爱视频| 蜜臀久久久99精品久久久久久| 国产精品成人一区| 亚洲国产精品久久久久秋霞蜜臀 | aⅴ色国产欧美| 久久久免费精品| 国产精品女人网站| 亚洲伦理久久| 久久手机精品视频| 亚洲一区二区三区在线| 欧美另类99xxxxx| 精品动漫3d一区二区三区免费| 亚洲欧美激情精品一区二区| 欧美成人免费视频| 久久久久9999亚洲精品|