前言
考得很烂
szy 好强！！！
赛时得分明细：
| hugclose | wayhome | jewel | Tolal | rank |
|---|---|---|---|---|
| 6 | 10 | 0 | 16 | 20 |
赛后改题明细：
| hugclose | wayhome | jewel |
|---|---|---|
| 100 | 100 | 100 |
曾经的王牌累了
hugclose
题面
给定 \(n\) 个数，\(Q\) 个询问。每一次询问给出一个 \(x\)，问 \(\max\limits_{i=l}^r a_i \oplus x\)。
题解
他们都说是可持久化01-trie板子，不过我没学过。看来，得先自己学一遍。
其实它和可持久化线段树2的思路差不多。对于 \(n\) 个点，每一个点都对其做一个前缀可持久化01-trie。
然后再将 \(l-1\) 和 \(r\) 两棵树的信息合并。不过信息合并的和可持久化线段树的信息合并不同，因为可持久化01-trie的前后形态不同。所以我们要记录一个 \(siz_i\) 表示以第 \(i\) 个节点为根的子树节点个数。
由于需要异或值最大。每次贪心的从根节点走，如果 \(x\) 的第 \(i\) 位为 \(1\)，那么就走 \(0\)，否则就走 \(1\)。因为每个数的二进制长度不相同，所以建出来树可能会“参差不齐”，为了避免这种情况。我们应把每一个数的二进制前补零，使得每一个数形成的链长度相同。
一个点是否能跳取决于其子树大小是否比 \(l-1\) 棵树上相同位置上的子树要大，如果大，则说明有新数加入进来了，反之则没有。
然后就是一些细节问题：
Q：\(l-1\) 和 \(r\) 树上的两个指针再同时跳的时候，由于树的形态不相同。有可能会出现一个指针跳出去了，一个指针还在树上的情况。这个要怎么处理。
A：其实不用管跳出去的指针，因为指针记录的空节点的子树大小为零。
还得多多学算法，看眼界。
代码
#include <bits/stdc++.h>
#define int long long
#define H 19260817
#define rint register int
#define For(i,l,r) for(rint i=l;i<=r;++i)
#define FOR(i,r,l) for(rint i=r;i>=l;--i)
#define MOD 1000003
#define mod 1000000007
using namespace std;
inline int read() {
rint x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
void print(int x){
if(x<0){putchar('-');x=-x;}
if(x>9){print(x/10);putchar(x%10+'0');}
else putchar(x+'0');
return;
}
const int N = 2e5 + 10;
int n, q, t[N<<5][2], root[N<<5], siz[N<<5], idx, a[N];
void insert(int x, int y, int val) {
siz[y] = siz[x] + 1;
for (int i = 31; i >= 0; --i) {
int o = (val >> i) & 1;
t[y][o^1] = t[x][o^1];
if(!t[y][o]) t[y][o] = ++idx;
y = t[y][o];
x = t[x][o];
siz[y] = siz[x] + 1;
}
}
int query(int x, int y, int val) {
int ans = 0;
for (int i = 31; i >= 0; i--) {
int o = (val >> i) & 1;
if(siz[t[x][o ^ 1]] < siz[t[y][o ^ 1]]) {
ans += (1 << i);
x = t[x][o ^ 1];
y = t[y][o ^ 1];
} else {
x = t[x][o];
y = t[y][o];
}
}
return ans;
}
signed main() {
// freopen("hugclose.in", "r", stdin);
// freopen("hugclose.out", "w", stdout);
n = read(), q = read();
For(i,1,n) {
a[i] = read();
root[i] = ++idx;
insert(root[i - 1], root[i], a[i]);
}
while(q--) {
int x = read(), l = read(), r = read();
l++, r++;
cout << query(root[l-1], root[r], x) << '\n';
}
return 0;
}
wayhome
题面
Jim 走夜路很怕黑，时时刻刻需要手电筒。有 \((N+1)\) 个充电站，\(0\) 是起点 \(N\) 是终点。第 \(i\) 个充电站到下一个充电站的距离为 \(D_i\)，单位充电量花费为 \(P_i\)。每移动一个单位长度电量消耗一个单位电。如果 Jim 无法保证全程
手电筒都亮着输出 \(-1\)。否则求整个旅途的最少花费。
题解
贪心。
对于走到的每一个充电桩，贪心的选择此时充或不充。每一次判断剩余电量到下一个比此充电桩 \(P_i\) 更小的充电桩是否足够。若不足够，则把电量充满，到下一个充电桩做同样的贪心决策；反之，则将电量充到到下一个比此充电桩 \(P_i\) 更小的充电桩所需的电量。这样可以保证到了那一个点电量可以用完，并且充到廉价的电。、
找下一个比此充电桩 \(P_i\) 更小的充电桩可以用单调栈。然后模拟即可。
代码
#include <bits/stdc++.h>
#define int long long
#define H 19260817
#define rint register int
#define For(i,l,r) for(rint i=l;i<=r;++i)
#define FOR(i,r,l) for(rint i=r;i>=l;--i)
#define MOD 1000003
#define mod 1000000007
using namespace std;
inline int read() {
rint x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
void print(int x){
if(x<0){putchar('-');x=-x;}
if(x>9){print(x/10);putchar(x%10+'0');}
else putchar(x+'0');
return;
}
const int N = 5e5 + 10;
int n, d[N], p[N], T, sum[N], stk[N], top, nx[N], ans, ram;
signed main() {
n = read(), T = read();
For(i,1,n) {
d[i] = read(), p[i] = read();
sum[i] = sum[i - 1] + d[i];
}
For(i,1,n) {
while(top && p[stk[top]] > p[i]) {
nx[stk[top]] = i;
top--;
}
stk[++top] = i;
}
while(top) {
nx[stk[top--]] = n+1;
}
ram = 0;
for (int i = 1; i <= n; i++) {
ram -= d[i-1];
if(ram < 0) {
puts("-1");
return 0;
}
int dis = min(sum[nx[i]-1] - sum[i-1], T);
if(dis > ram) ans += (dis - ram) * p[i], ram = dis;
}
cout << ans << '\n';
return 0;
}
jewel
题面
给定 \(n\) 个数，\(m\) 次询问。每次询问给出 \(l, r\)，求 \(\min\limits_{l\le x<y\le n}^{a_x = a_y} |x-y|\)。
题解
考场上想出来了，但没做出来（原因是线段树没有 pushup）。
记 \(d_i\) 表示从左往右第一个与 \(i\) 位置上的数相等的距离。下意识就是转化为区间最小值。线段树维护即可。
不过你会发现 \(d_i\) 的答案贡献和区间有关。但只和区间右端点有关。于是将询问离线，按右端点排序。再维护 \(d_i\) 的区间最小值，单点修改，线段树能胜任。右端点没变，直接查区间最小。右端点变动，将变动的部分区间的贡献删去，再查区间最小。
“将变动的部分区间的贡献删去”这一操作还需维护一个 \(t_i\) 表示从 \(i\) 这个数往左看第一个等于 \(i\) 这个位置上的数的位置。然后当右端点变动的时候，将变动的部分区间所对应的 \(t_i\) 暴力修改即可。（每个点最多只会被修改一次，所以时间复杂度依然为 \(O((q+n)\log n)\)）。
代码
#include <bits/stdc++.h>
#define int long long
#define H 19260817
#define rint register int
#define For(i,l,r) for(rint i=l;i<=r;++i)
#define FOR(i,r,l) for(rint i=r;i>=l;--i)
#define MOD 1000003
#define mod 1000000007
#define inf 0x3f3f3f3f3f3f3f3f
#define ls p<<1
#define rs p<<1|1
using namespace std;
inline int read() {
rint x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
void print(int x){
if(x<0){putchar('-');x=-x;}
if(x>9){print(x/10);putchar(x%10+'0');}
else putchar(x+'0');
return;
}
const int N = 5e5 + 10;
int n, a[N], d[N], last[N], q, ans[N], tt[N], lr;
vector<int> v;
int find(int x) {
return lower_bound(v.begin(), v.end(), x) - v.begin() + 1;
}
struct Segtree {
int l, r, mi;
} t[N << 2];
struct Node {
int l, r, id;
bool operator < (const Node &x) const {
if(x.r != r) return x.r < r;
return x.l < l;
}
} Q[N];
void pushup(int p) {
t[p].mi = min(t[ls].mi, t[rs].mi);
}
void build(int p, int l, int r) {
t[p].l = l, t[p].r = r;
if(l == r) {
t[p].mi = d[l];
return ;
}
int mid = (l + r) >> 1;
build(ls, l, mid);
build(rs, mid + 1, r);
pushup(p);
}
int query(int p, int l, int r) {
if(l <= t[p].l && t[p].r <= r) {
return t[p].mi;
}
int mid = (t[p].l + t[p].r) >> 1, ans = inf;
if(l <= mid) ans = min(ans, query(ls, l, r));
if(r > mid) ans = min(ans, query(rs, l, r));
return ans;
}
void up(int p, int x, int v) {
if(t[p].l == t[p].r) {
t[p].mi = v;
return ;
}
int mid = (t[p].l + t[p].r) >> 1;
if(x <= mid) up(ls, x, v);
else up(rs, x, v);
pushup(p);
}
signed main() {
// freopen("jewel.in", "r", stdin);
// freopen("jewel.out", "w", stdout);
n = read(), q = read();
For(i,1,n) a[i] = read(), v.push_back(a[i]);
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
FOR(i,n,1) last[i] = inf;
FOR(i,n,1) d[i] = (last[find(a[i])] == inf ? inf : last[find(a[i])] - i), last[find(a[i])] = i;
For(i,1,n) last[i] = inf;
For(i,1,n) tt[i] = (last[find(a[i])] == inf ? inf : last[find(a[i])]), last[find(a[i])] = i;
For(i,1,q) Q[i] = (Node) {read(), read(), i};
sort(Q + 1, Q + q + 1);
build(1, 1, n);
lr = n;
For(i,1,q) {
int l = Q[i].l, r = Q[i].r;
if(lr == r) ans[Q[i].id] = query(1, l, r);
else {
int L = r + 1, R = lr;
For(j,L,R) {
if(tt[j] != inf) up(1, tt[j], inf);
}
ans[Q[i].id] = query(1, l, r);
}
lr = r;
}
For(i,1,q) {
cout << (ans[i] == inf ? -1 : ans[i]) << '\n';
}
return 0;
}