CodeForces 1136 E 和 D 题 有意思的题
题目链接:here
原题目描述在最下面
先更新E题
CF 1136E 线段树
题意:
给你两个序列和。输入保证。
两种操作:区间求和给单点加。
第二个操作有连锁反映,若,则更新为,同理更新直到不能更新为止。
思路:
在纸上画画,你会发现:。
给位置加上值之后,也增加了。更新之前已知:,如果,那么,并且。同理更新。
你发现了什么?
我们令,我们给单点加上之后的效果是:把间所有小于的全部赋值为。
到这里思路就很明显了。我们用线段树维护即可,求和就是;更新就是区间赋值操作,因为满足单调不递减,所以你可以二分出右端点来。
本题结束。
AC_code
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
const LL lt = -1e18;
const int INF = 0x3f3f3f3f;
const int MXN = 1e5 + 7;
int n, m;
LL ar[MXN], kr[MXN], kk[MXN];
LL sum[MXN<<2], flag[MXN<<2], Max[MXN<<2];
void build(int l, int r, int rt) {
flag[rt] = lt;
if(l == r) {
sum[rt] = ar[l] - kr[l-1];
return;
}
int mid = (l + r) >> 1;
build(l, mid, rt<<1); build(mid+1, r, rt<<1|1);
sum[rt] = sum[rt<<1] + sum[rt<<1|1];
}
void push_down(int l, int mid, int r, int rt) {
if(flag[rt] == lt) return;
flag[rt<<1] = flag[rt];
flag[rt<<1|1] = flag[rt];
sum[rt<<1] = flag[rt] * (mid-l+1);
sum[rt<<1|1] = flag[rt] * (r-mid);
flag[rt] = lt;
}
void update(int L, int R, LL v, int l, int r, int rt) {
if(L <= l && r <= R) {
flag[rt] = v;
sum[rt] = v * (r-l+1);
return;
}
int mid = (l + r) >> 1;
push_down(l, mid, r, rt);
if(L > mid) update(L,R,v,mid+1,r,rt<<1|1);
else if(R <= mid) update(L,R,v,l,mid,rt<<1);
else {
update(L,mid,v,l,mid,rt<<1);
update(mid+1,R,v,mid+1,r,rt<<1|1);
}
sum[rt] = sum[rt<<1]+sum[rt<<1|1];
}
LL query(int L, int R, int l, int r, int rt) {
if(L > R) return 0;
if(L <= l && r <= R) return sum[rt];
int mid = (l+r)>>1;
push_down(l, mid, r, rt);
if(L > mid) return query(L,R,mid+1,r,rt<<1|1);
else if(R <= mid) return query(L,R,l,mid,rt<<1);
else {
return query(L,mid,l,mid,rt<<1)+query(mid+1,R,mid+1,r,rt<<1|1);
}
}
int main() {
scanf("%d", &n);
for(int i = 1; i <= n; ++i) scanf("%lld", &ar[i]);
for(int i = 1; i < n; ++i) scanf("%lld", &kr[i]);
for(int i = 2; i < n; ++i) kr[i] += kr[i-1];
for(int i = 1; i < n; ++i) kk[i] = kk[i-1] + kr[i];
build(1, n, 1);
int Q; scanf("%d", &Q);
char s[2]; int l, r;
while(Q --) {
scanf("%s%d%d", s, &l, &r);
if(s[0] == 's') {
printf("%lld\n", query(l,r,1,n,1)+kk[r-1]-(l>=2?kk[l-2]:0));
}else {
int L = l, R = n, mid, ans = l;
ar[l] = query(l,l,1,n,1) + r;
//printf("*%lld\n", ar[l]);
while(L <= R) {
mid = (L+R) >> 1;
if(ar[l] > query(mid,mid,1,n,1)) {
ans = mid;
L = mid+1;
}else R = mid-1;
}
//printf("%d\n", ans);
update(l, ans, ar[l], 1, n, 1);
}
}
return 0;
}
CF 1136D 贪心
题意:
思路:
AC_code
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int MXN = 5e5 + 7;
int n, m;
int is[MXN];
int ls[MXN], rs[MXN];
std::vector<int> mp[MXN];
int main() {
#ifndef ONLINE_JUDGE
freopen("E://ADpan//in.in", "r", stdin);
//freopen("E://ADpan//out.out", "w", stdout);
#endif
scanf("%d%d", &n, &m);
for(int i = 1, x; i <= n; ++i) scanf("%d", &x), is[x] = i;
for(int i = 0, a, b; i < m; ++i) {
scanf("%d%d", &a, &b); a = is[a], b = is[b];
mp[b].push_back(a);
if(b == n) ++ rs[a];
}
int ans = 0;
for(int i = n - 1; i >= 1; --i) {
//printf("%d %d\n", i, rs[i]);
if(rs[i] == n - i - ans) {
++ ans;
}else {
for(int x: mp[i]) ++ rs[x];
}
}
printf("%d\n", ans);
#ifndef ONLINE_JUDGE
cout << "time cost:" << clock() << "ms" << "\n";
#endif
return 0;
}