• 欢迎光临~

# Educational Codeforces Round 132 (Rated for Div. 2)

## B

### 代码

```#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "n"
const int N = 2e5 + 7, INF = 1e18;
int s[N], d1[N], d2[N];
void solve()
{
int n, m;
cin >> n >> m;
s[0] = d1[0] = d2[0] = 0;
d2[n + 1] = 0;
for (int i = 1; i <= n; i++)
{
cin >> s[i];
d1[i] = 0, d2[i] = 0;
}
for (int i = 1; i <= n; i++)
{
d1[i] += d1[i - 1];
if (s[i] < s[i - 1])
d1[i] += s[i - 1] - s[i];
}
for (int i = n; i >= 1; i--)
{
d2[i] += d2[i + 1];
if (s[i] < s[i + 1])
d2[i] += s[i + 1] - s[i];
}
for (int i = 1; i <= m; i++)
{
int a, b;
cin >> a >> b;
if (a < b)
{
cout << d1[b] - d1[a] << endl;
}
else
{
cout << d2[b] - d2[a] << endl;
}
}
}

signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
// cin >> t;
while (t--)
{
solve();
}

return 0;
}```

## D

### 代码

```#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "n"
const int N = 2e5 + 7, INF = 1e18;
int mid, n, ka, d[N];
struct D
{
int l, r;
int v;
} s[N * 4];
void bulid(int u, int l, int r)
{
s[u] = {l, r};
if (l == r)
{
s[u].v = d[l];
return;
}
int mod = (l + r) >> 1;
bulid(u << 1, l, mod), bulid(u << 1 | 1, mod + 1, r);
s[u].v = max(s[u << 1].v, s[u << 1 | 1].v);
}

void add(int u, int x, int v)
{
if (s[u].l == x && s[u].r == x)
{
s[u].v = v;
return;
}
int mod = (s[u].l + s[u].r) >> 1;
if (x <= mod)
add(u << 1, x, v);
else
add(u << 1 | 1, x, v);
s[u].v = max(s[u << 1].v, s[u << 1 | 1].v);
}
int fins(int u, int l, int r)
{
if (s[u].l >= l && s[u].r <= r)
return s[u].v;
int cnt = 0;
int mod = (s[u].l + s[u].r) >> 1;
if (mod >= l)
cnt = fins(u << 1, l, r);
if (mod < r)
cnt = max(cnt, fins(u << 1 | 1, l, r));
return cnt;
}

void solve()
{
int n, m;
cin >> n >> m;
for (int i = 1; i <= m; i++)
cin >> d[i];
bulid(1, 1, N);
int t;
cin >> t;
while (t--)
{
int x1, y1, x2, y2, k;
cin >> y1 >> x1 >> y2 >> x2 >> k;
if (abs(x1 - x2) % k == 0 && abs(y1 - y2) % k == 0)
{
int sa = (n - y1) / k;
y1 += k * sa;
if (x1 > x2)
swap(x1, x2);
int fsa = fins(1, x1, x2);
if (y1 > fsa)
{
cout << "YESn";
continue;
}
else
{
cout << "NOn";
continue;
}
}
else
{
cout << "NOn";
continue;
}
}
}

signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
;
int _ = 1;
// cin>>_;
while (_--)
solve();
}```