【题目链接】:http://codeforces.com/problemset/problem/500/E
【题意】
有n个多米诺骨牌;
你知道它们的长度;
然后问你,如果把第i骨牌往后推倒,然后要求第i到第j个骨牌(j>i)都倒掉;
问你需要把i..j这里面骨牌总共增高多少单位的长度(输出最小值);
【题解】
从最后一个骨牌开始往前处理;
对于每一个骨牌,把p[i]..p[i]+l[i]全都覆盖;
然后对于询问x[i],y[i];
即查询p[x[i]]..p[y[i]]这个区间里面有多少个空格;
这两个操作都能用线段树完成;
写线段树的时候要写坐标压缩.
【Number Of WA】
6
【完整代码】
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#include <bits/stdc++.h>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define ms(x,y) memset(x,y,sizeof x)
#define Open() freopen("F:\rush.txt","r",stdin)
#define Close() ios::sync_with_stdio(0),cin.tie(0)
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;
const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};
const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};
const double pi = acos(-1.0);
const int N = 2e5+100;
const int MAX_SIZE = 4e5+100;
int n,q,ma;
int p[N],l[N];
vector <pii> v[N];
map <int,int> dic;
vector <int> t;
int ans[N],lazy_tag[MAX_SIZE<<2],sum[MAX_SIZE<<2];
void push_down(int rt,int l,int r)
{
if (lazy_tag[rt]==0) return;
lazy_tag[rt] = 0;
sum[rt] = t[r+1]-t[l];
if (l!=r)
lazy_tag[rt<<1] = lazy_tag[rt<<1|1] = 1;
}
void up_data(int L,int R,int l ,int r,int rt)
{
push_down(rt,l,r);
if (L <= l && r <= R)
{
lazy_tag[rt] = 1;
push_down(rt,l,r);
return;
}
int m = (l+r)>>1;
if (L <= m)
up_data(L,R,lson);
if (m < R)
up_data(L,R,rson);
push_down(rt<<1,l,m);push_down(rt<<1|1,m+1,r);
sum[rt] = sum[rt<<1] + sum[rt<<1|1];
}
int query(int L,int R,int l,int r,int rt)
{
//cout <<L<<' '<<R<<' '<<l<<' '<<r<<' '<<endl;
push_down(rt,l,r);
if (L<=l && r <= R)
return sum[rt];
int m = (l+r)>>1;
int temp1 = 0,temp2 = 0;
if (L<=m)
temp1=query(L,R,lson);
if (m<R)
temp2=query(L,R,rson);
//cout <<temp1+temp2<<endl;
return temp1+temp2;
}
int main()
{
ms(sum,0);
ms(lazy_tag,0);
// Open();
Close();//scanf,puts,printf not use
//init??????
cin >> n;
t.pb(-1);
rep1(i,1,n)
{
cin >> p[i] >> l[i];
if (!dic[p[i]])
{
dic[p[i]] = 1;
t.pb(p[i]);
}
if (!dic[p[i]+l[i]])
{
dic[p[i]+l[i]] = 1;
t.pb(p[i]+l[i]);
}
}
sort(t.begin(),t.end());
ma = int(t.size())-1;
dic.clear();
rep1(i,1,ma)
dic[t[i]] = i;
cin >> q;
rep1(i,1,q)
{
int x,y;
cin >>x >> y;
v[x].pb(mp(y,i));
}
rep2(i,n,1)
{
int xb1 = dic[p[i]],xb2 = dic[p[i]+l[i]];
//cout <<xb1<<' '<<xb2<<endl;
//cout <<xb1<<' '<<xb2<<endl;
up_data(xb1,xb2-1,1,ma-1,1);
//if (i==3)
//{
//
cout <<xb1<<' '<<xb2<<endl;
//
return 0;
// }
//cout <<dic[p[i]]<<' '<<dic[p[i+1]]<<endl;
//cout <<xb1<<' '<<xb2<<endl;
//cout << query(dic[p[i]],dic[p[i+1]]-1,1,ma,1) << endl;
//return 0;
int len = v[i].size();
rep1(j,0,len-1)
{
int w = v[i][j].fi,id = v[i][j].se;
int xb3 = dic[p[w]];
//cout <<xb1<<' '<<xb3-1<<endl;
ans[id] = p[w]-p[i]-query(xb1,xb3-1,1,ma-1,1);
//cout <<p[w]-p[i]<<endl;
//cout <<query(xb1,xb3-1,1,ma-1,1)<<endl;
}
}
rep1(i,1,q)
cout << ans[i] << endl;
return 0;
}
最后
以上就是精明摩托最近收集整理的关于【codeforces 500E】New Year Domino的全部内容，更多相关【codeforces内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复