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

oyjpArt ACM/ICPC算法程序設計空間

// 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)
 * 考慮到轉移的時候選擇的是一段內的最小dp值,運用點樹可以解決
 */
#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 新寫的線段樹(點樹)模版  回復  更多評論   

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

# re: pku1769 新寫的線段樹(點樹)模版  回復  更多評論   

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

# re: pku1769 新寫的線段樹(點樹)模版  回復  更多評論   

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

# re: pku1769 新寫的線段樹(點樹)模版  回復  更多評論   

2008-01-18 12:40 by oyjpart
你的樣例是無解的,沒有線段覆蓋【0,10】的區間。

# re: pku1769 新寫的線段樹(點樹)模版  回復  更多評論   

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 新寫的線段樹(點樹)模版  回復  更多評論   

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

# re: pku1769 新寫的線段樹(點樹)模版  回復  更多評論   

2008-04-18 10:44 by l-y-p
向大牛學習學習,“運用點樹可以解決”,好思想,很好很強大。但是還有一個疑點:在DP的時候應該從小到大進行,但是沒發現你對y坐標進行排序就直接進行,那如果是考慮這樣兩組數據:
10 40
0 10
從10到40先確定到40的DP值為maxint+1,然后再由0~10確定10的值為1,這樣是不是有問題??你的程序我沒調試過,不曉得你是怎么處理的?

# re: pku1769 新寫的線段樹(點樹)模版  回復  更多評論   

2008-04-18 10:58 by l-y-p
果然啊,剛調試了下,直接運行數據:
40 2
10 40
0 10
結果是1000000000,不知道是我沒看清楚還是程序的bug?

# re: pku1769 新寫的線段樹(點樹)模版  回復  更多評論   

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

# re: pku1769 新寫的線段樹(點樹)模版  回復  更多評論   

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

# re: pku1769 新寫的線段樹(點樹)模版  回復  更多評論   

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

# re: pku1769 新寫的線段樹(點樹)模版  回復  更多評論   

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

# re: pku1769 新寫的線段樹(點樹)模版  回復  更多評論   

2010-12-01 20:36 by LSK
請仔細讀題。。。ZJU哪個是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>
            欧美性猛交一区二区三区精品| 欧美成人免费网| 亚洲午夜精品在线| 欧美日韩在线播放一区二区| 一区二区高清| 亚洲一区二区三区在线看| 国产视频一区在线观看| 久久久一本精品99久久精品66| 久久都是精品| 亚洲国产欧美日韩| 日韩午夜av| 国产日韩一区二区三区在线播放| 久久精品99久久香蕉国产色戒 | 久久国产欧美精品| 国产日产高清欧美一区二区三区| 亚洲一级黄色av| 一区二区三区视频在线观看| 欧美日韩在线精品一区二区三区| 亚洲精品免费在线播放| 欧美激情五月| 欧美日韩一区三区| 亚洲少妇诱惑| 亚洲小少妇裸体bbw| 国产精品爽黄69| 久久精品一区二区三区中文字幕| 久久精品天堂| 亚洲精品男同| 亚洲精品综合| 国产精品一区二区久激情瑜伽| 欧美一区二区精品久久911| 欧美怡红院视频一区二区三区| 一区二区在线视频播放| 亚洲国产三级在线| 国产精品成人观看视频国产奇米| 欧美一区二区日韩| 浪潮色综合久久天堂| 一道本一区二区| 日韩视频不卡中文| 欧美色视频一区| 欧美 日韩 国产一区二区在线视频| 欧美大片一区二区| 亚洲欧美国内爽妇网| 久久精品欧美| 亚洲免费一级电影| 久久久久九九九九| 亚洲精品日韩欧美| 国产精品一区二区久久国产| 美女视频黄 久久| 欧美日韩高清在线| 老司机久久99久久精品播放免费| 欧美精品一区二区三区很污很色的| 欧美一级理论片| 久久久久国产精品人| 亚洲国产一区在线观看| 亚洲清纯自拍| 激情综合亚洲| 午夜精品理论片| 亚洲乱码视频| 久久婷婷av| 亚洲欧美一级二级三级| 榴莲视频成人在线观看| 日韩天堂在线观看| 久久久人人人| 久久久777| 国产精品你懂得| 亚洲免费观看高清在线观看| 亚洲国产欧美不卡在线观看| 欧美一区二区性| 欧美一区三区三区高中清蜜桃| 久久精品综合| 欧美一区二区三区电影在线观看| 国产精品推荐精品| 夜夜精品视频| 日韩视频免费| 欧美成人精品| 欧美jizzhd精品欧美巨大免费| 国产欧美日韩精品丝袜高跟鞋| 91久久综合亚洲鲁鲁五月天| 亚洲国产精品成人久久综合一区| 久久aⅴ国产紧身牛仔裤| 香蕉免费一区二区三区在线观看 | 亚洲日韩中文字幕在线播放| 这里只有精品视频| 亚洲欧洲在线一区| 嫩草国产精品入口| 亚洲福利国产| 在线播放国产一区中文字幕剧情欧美 | 久久成人精品视频| 久久免费国产精品1| 国产自产v一区二区三区c| 欧美一级视频精品观看| 久久国产手机看片| 国产一区清纯| 久久男人资源视频| 亚洲激情另类| 亚洲网站在线观看| 国产精品视频一二| 亚洲天堂第二页| 午夜精品免费视频| 亚洲国产婷婷香蕉久久久久久99| 久久亚洲国产成人| 亚洲国产高清在线观看视频| 亚洲日本电影| 欧美视频免费| 性色av一区二区三区红粉影视| 久久久7777| 国产亚洲在线观看| 久久免费视频一区| 亚洲国产精选| 午夜精品福利在线| 国产欧美精品一区| 久久一区二区视频| 欧美ed2k| 亚洲在线黄色| 国产精品亚发布| 亚洲视频精品在线| 欧美激情精品久久久久久| 亚洲视频一二| 影音先锋一区| 欧美激情按摩| 亚洲欧美中文另类| 欧美激情一区二区三区不卡| 亚洲一区二区三区视频播放| 国产精品久久网| 久久美女性网| 洋洋av久久久久久久一区| 久久国产精品黑丝| 亚洲第一天堂av| 国产精品久久久久久久久免费 | 亚洲精品网站在线播放gif| 国产精品video| 老司机午夜精品视频| 亚洲欧洲久久| 亚洲高清不卡一区| 久久福利毛片| 亚洲一区二区在线播放| 亚洲黄色免费网站| 国产一区二区三区免费不卡| 欧美人与性禽动交情品| 欧美在线免费一级片| 99精品99| 亚洲国产精品福利| 免费成人高清| 久久久久女教师免费一区| 亚洲一区三区视频在线观看| 亚洲精品中文字幕有码专区| 好吊视频一区二区三区四区| 国产欧美三级| 国产精品毛片在线看| 欧美日韩三级| 国产精品视频第一区| 欧美日韩在线视频首页| 美女主播视频一区| 久久天天躁狠狠躁夜夜爽蜜月| 篠田优中文在线播放第一区| 亚洲一级免费视频| 夜夜精品视频| av不卡在线| 一本久久a久久免费精品不卡| 久久精品国产2020观看福利| 久久国产精彩视频| 久久国产精品一区二区三区| 亚洲欧美日韩国产| 亚洲欧美日韩一区在线观看| 亚洲欧美偷拍卡通变态| 亚洲在线第一页| 日韩一级裸体免费视频| 在线国产精品播放| 亚洲欧洲另类国产综合| 亚洲电影自拍| 日韩视频二区| 亚洲综合视频一区| 欧美伊人久久久久久午夜久久久久 | 99人久久精品视频最新地址| 一区二区高清在线观看| 亚洲一区区二区| 欧美一区激情| 美女精品自拍一二三四| 另类av一区二区| 欧美日韩一区二区三区四区五区 | 9国产精品视频| 亚洲一区日本| 久久深夜福利| 欧美日韩三级电影在线| 国产婷婷色一区二区三区四区| 国产一区二区三区在线观看免费 | 久久综合狠狠| 欧美成年视频| 国产精品久久久久永久免费观看| 国产精品资源| 亚洲人精品午夜在线观看| 亚洲精品国产精品乱码不99按摩| 日韩亚洲欧美高清| 亚洲欧美在线观看| 亚洲电影下载| 亚洲欧美视频一区二区三区| 久久这里有精品视频| 欧美日韩国产美女| 激情综合中文娱乐网| 一级日韩一区在线观看|