目录
问题概述
原题参考G.新春漫步
坐标轴上有n个点,初始时每个位置上都有一个坚固程度为a1的障碍物,接下来有m次操作
1.将位置p上的障碍物的坚固程度减去x,若减去x后坚固程度小于等于0,则该障碍物消失
2.询问一个人从p的位置向右走,最多能走到什么位置(停在遇到的第一个障碍物的位置)
思路分析
赛时看到这个题我还是比较惊喜的,首先操作一就是属于单点修改,操作二是啥,简单分析一下嘛,从p位置开始走,直到第一个障碍物停止,那么期间走过的位置的坚固值不全都是0嘛,那么不就是查询最长的区间和为0的区间嘛,那这就是区间查询的操作嘛,这个又可以用二分进行简化,但是二分简化之后要进行一次特判;因为使用二分的话区间查询最小区间是2,不能判断当前位置是否是0,大致倒是很类似最近LCA的第二次跳点的做法
参考代码
#include <bits/stdc++.h>
using namespace std;
#define FAST_IO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'
#define pll pair<long long, long long>
#define pii pair<int, int>
#define vi vector<int>
#define vl vector<long long>
#define ll long long
#define ull unsigned long long
const ll INF = 9187201950435737471;
const int inf = 2139062143;
const ll mod = 1e9 + 7;
const double eps = 1e-6;
const double PI = acos(-1.0);
const int N = 1e6+7;
ll n, m, a[N];
ll getL(int idx) {return idx<<1;}
ll getR(int idx) {return idx<<1|1;}
ll sum(ll a, ll b) {return a+b;}
struct node {
ll nSum;
} t[N*4];
inline ll read() {
//使用快读记得别关流 会tle的
ll res = 0, mark = 1;
char ch = getchar();
while(ch < '0' || ch > '9') {
if(ch == '-') mark = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9') {
res = (res<<1) + (res<<3) + (ch^48);
ch = getchar();
}
return res * mark;
}
inline void write(int x) {
if(x < 0) {
putchar('-');
x = -x;
}
if(x > 9) write(x/10);
putchar(x%10 + '0');
}
void update(int idx) {
t[idx].nSum = sum(t[getL(idx)].nSum, t[getR(idx)].nSum);
}
void build(int idx, int lt, int rt) {
if(lt == rt) t[idx].nSum = a[lt];
else {
int mid = (lt+rt) >> 1;
build(getL(idx), lt, mid);
build(getR(idx), mid+1, rt);
update(idx);
}
}
void change(int idx, int lt, int rt, int cidx, int add) {
if(lt == rt) {
t[idx].nSum += add;
if(t[idx].nSum < 0) t[idx].nSum = 0;
}
else {
int mid = (lt+rt) >> 1;
if(cidx <= mid) change(getL(idx), lt, mid, cidx, add);
else change(getR(idx), mid+1, rt, cidx, add);
update(idx);
}
}
ll query(int idx, int lt, int rt, int ql, int qr) {
ll ans = 0;
if(lt == ql && rt == qr) ans += t[idx].nSum;
else {
ll mid = (lt+rt) >> 1;
if(qr <= mid) ans += query(getL(idx), lt, mid, ql, qr);
else if(ql > mid) ans += query(getR(idx), mid+1, rt, ql, qr);
else ans += sum(query(getL(idx), lt, mid, ql, mid), query(getR(idx), mid+1, rt, mid+1, qr));
}
return ans;
}
void solve() {
n = read(), m = read();
for(int i=1; i<=n; i++) a[i] = read();
build(1, 1, n);
while(m --) {
int op, p, q;
op = read(), p = read();
if(op == 1) {
q = read();
change(1, 1, n, p, -q);
}
else {
int lt = p, ans = p;
for(int i=20; i>=0; i--) {
if(lt+(1ll<<i) > n) continue;
if(!query(1, 1, n, lt, lt+(1ll<<i))) {
lt = lt+(1ll<<i);
ans = lt;
}
}
if(!query(1, 1, n, ans, ans) && ans < n) ans ++;
write(ans);
putchar('\n');
}
}
}
int main() {
#ifdef xrl
freopen("in.txt", "r", stdin), freopen("out.txt", "w", stdout);
#endif
//FAST_IO;
int t = 1;
//cin >> t;
while(t --) solve();
#ifdef xrl
cout << "Time used = " << (double)(clock() * 1.0 / CLOCKS_PER_SEC) << "s";
#endif
return 0;
}
做题反思
说实话,赛时的第一发不是线段树,而是树状数组,但是由于对树状数组的理解不是很深,导致修改的时候出现了问题,就是我没有记录原数组,不得而知该次操作是否对树状数组生效,当然,这是赛后想出来的了;赛时还是用线段树写的,经此一役,我再也不会因为线段树的空间复杂度嫌弃线段树了,毕竟它都没嫌弃我蠢,emmm
第二,以后我遇到大量样例输入,请使用较快的输入输出
这句话时,我尼玛一定要用快读快写,今日是从关流的cin->scanf->quickread,诶,就是喜欢超时,怎么了!!!