程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> Codeforces 500E. New Year Domino 倍增/線段樹+離線

Codeforces 500E. New Year Domino 倍增/線段樹+離線

編輯:關於C++

 

 

 

E. New Year Domino time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output

Celebrating the new year, many people post videos of falling dominoes; Here's a list of them:https://www.youtube.com/results?search_query=New+Years+Dominos

User ainta, who lives in a 2D world, is going to post a video as well.

There are n dominoes on a 2D Cartesian plane. i-th domino (1?≤?i?≤?n) can be represented as a line segment which is parallel to the y-axis and whose length is li. The lower point of the domino is on the x-axis. Let's denote the x-coordinate of the i-th domino as pi. Dominoes are placed one after another, so p1?p2?pn?-?1?pn holds.

User ainta wants to take a video of falling dominoes. To make dominoes fall, he can push a single domino to the right. Then, the domino will fall down drawing a circle-shaped orbit until the line segment totally overlaps with the x-axis.

\

Also, if the s-th domino touches the t-th domino while falling down, the t-th domino will also fall down towards the right, following the same procedure above. Domino s touches domino t if and only if the segment representing s and t intersects.

\

See the picture above. If he pushes the leftmost domino to the right, it falls down, touching dominoes (A), (B) and (C). As a result, dominoes (A), (B), (C) will also fall towards the right. However, domino (D) won't be affected by pushing the leftmost domino, but eventually it will fall because it is touched by domino (C) for the first time.

\

The picture above is an example of falling dominoes. Each red circle denotes a touch of two dominoes.

User ainta has q plans of posting the video. j-th of them starts with pushing the xj-th domino, and lasts until the yj-th domino falls. But sometimes, it could be impossible to achieve such plan, so he has to lengthen some dominoes. It costs one dollar to increase the length of a single domino by 1. User ainta wants to know, for each plan, the minimum cost needed to achieve it. Plans are processed independently, i. e. if domino's length is increased in some plan, it doesn't affect its length in other plans. Set of dominos that will fall except xj-th domino and yj-th domino doesn't matter, but the initial push should be on domino xj.

Input

The first line contains an integer n (2?≤?n?≤?2?×?105)— the number of dominoes.

Next n lines describe the dominoes. The i-th line (1?≤?i?≤?n) contains two space-separated integers pi, li (1?≤?pi,?li?≤?109)— the x-coordinate and the length of the i-th domino. It is guaranteed that p1?p2?pn?-?1?pn.

The next line contains an integer q (1?≤?q?≤?2?×?105) — the number of plans.

Next q lines describe the plans. The j-th line (1?≤?j?≤?q) contains two space-separated integers xj, yj (1?≤?xj?yj?≤?n). It means the j-th plan is, to push the xj-th domino, and shoot a video until the yj-th domino falls.

Output

For each plan, print a line containing the minimum cost needed to achieve it. If no cost is needed, print 0.

Sample test(s) input
6
1 5
3 3
4 4
9 2
10 1
12 1
4
1 2
2 4
2 5
2 6
output
0
1
1
2
Note

Consider the example. The dominoes are set like the picture below.

\

Let's take a look at the 4th plan. To make the 6th domino fall by pushing the 2nd domino, the length of the 3rd domino (whose x-coordinate is 4) should be increased by 1, and the 5th domino (whose x-coordinate is 9) should be increased by 1 (other option is to increase 4th domino instead of 5th also by 1). Then, the dominoes will fall like in the picture below. Each cross denotes a touch between two dominoes.

\
\
\
\
\

方法1: 就是求某一段區間沒有被覆蓋的長度是多少,可以離線詢問用線段樹解決

 

 

/* ***********************************************
Author        :CKboss
Created Time  :2015年03月23日 星期一 12時38分27秒
File Name     :CF500_2.cpp
************************************************ */

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include

using namespace std;

const int maxn=400100;

int n,q;

struct Gun 
{
	int h,l,r;
}gn[maxn];

struct QUE
{
	int l,r,ans,id; 
}que[maxn];

bool cmp1(QUE A,QUE B)
{
	if(A.l!=B.l) return A.l>B.l;
	return A.r>B.r;
}

bool cmp2(QUE A,QUE B)
{
	return A.idm) insert(L,R,rson);

	push_up(rt);
}

int query(int L,int R,int l,int r,int rt)
{
	if(L<=l&&r<=R)
	{
		return tree[rt];
	}

	push_down(l,r,rt);

	int m=(l+r)/2;

	int ret=0;
	if(L<=m) ret+=query(L,R,lson);
	if(R>m) ret+=query(L,R,rson);

	return ret;
}

int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);

	scanf("%d",&n);

	an++;
	for(int i=0;i=que[i].l-1)
		{
			/// add nx 加入第nx顆柱子
			int L=lower_bound(arr+1,arr+an,gn[nx].l)-arr;
			int R=lower_bound(arr+1,arr+an,gn[nx].r)-arr-1;
			insert(L,R,1,an-2,1);
			nx--;
		}

		int a = que[i].l-1 , b = que[i].r-1;
		int L=lower_bound(arr+1,arr+an,gn[a].l)-arr;
		int R=lower_bound(arr+1,arr+an,gn[b].l)-arr-1;

		que[i].ans=gn[b].l-gn[a].l-query(L,R,1,an-2,1);
	}

	sort(que,que+q,cmp2);

	for(int i=0;i

 

 

方法2: 倍增法預處理到前為2^j的線段是哪一個,距離是多少

 

 

/* ***********************************************
Author        :CKboss
Created Time  :2015年03月23日 星期一 21時39分56秒
File Name     :CF500E_3.cpp
/// 倍增法
************************************************ */

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include

using namespace std;

const int maxn=200200;
const int INF=2100000000;

int n;
int a[maxn],b[maxn];
int d[maxn],dn;

int p[maxn][20];
int q[maxn][20];

int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);

	scanf("%d",&n);
	for(int i=0;i=0;i--)
	{
		while(a[d[dn-1]]+b[d[dn-1]]<=a[i]+b[i]) dn--;
		p[i][0]=d[dn-1];
		if(a[i]+b[i]>=a[d[dn-1]]) q[i][0]=0;
		else q[i][0]=a[d[dn-1]]-a[i]-b[i];
		d[dn++]=i;
	}

	for(int j=1;j<20;j++)
	{
		for(int i=n;i>=0;i--)
		{
			p[i][j]=p[p[i][j-1]][j-1];
			q[i][j]=q[i][j-1]+q[p[i][j-1]][j-1];
		}
	}

	int T_T;
	scanf("%d",&T_T);
	while(T_T--)
	{
		int l,r,ans=0;
		scanf("%d%d",&l,&r);
		l--; r--;
		for(int i=19;i>=0;i--)
		{
			if(p[l][i]<=r)
			{
				ans+=q[l][i];
				l=p[l][i];
			}
		}
		printf("%d\n",ans);
	}

    return 0;
}


 

 

 

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved