Namomo spring camp Day3
树状数组上二分
可以支持单点修，查询前缀和小于等于/小于k的位置。
或者是求动态整体区间的第k大。建立值域树状数组
类似是，倍增去拼凑的思路。
int pos = 0;
for(int bit = 18;bit >= 0;bit --)
if(pos + (1<<bit) <= n && c[pos + (1<<bit)] <= s){
pos += 1<<bit;
s -= c[pos];
}
单调栈
G - Divide a Sequence
分析
这题杜爹分析的很快。思路确实奇妙，但是实现起来还是需要一定对单调栈的熟络，不然就会像我一样卡顿。
我们先推出了dp式子，\(dp_i = \sum_{j=0}^{i-1}dp_j*max_{k=0}^{j}a_k - \sum_{j=0}^{i-1}dp_j*min_{k=0}^{j}a_k\)。
如果我们暴力的话就是\(O(n^2)\)。
我们观察到如果使用单调栈来维护一个单调递减的序列，那么两个在单调栈中相邻的坐标，(stk[x]，stk[y]]，这一段的最值都是a[stk[y]]。
那么我们只要顺序的递推过去后，维护一个前缀和\(s_i = \sum_{j=1}^{j}dp_j\)，再维护一个\(sum_i = \sum_{j=0}^{i-1}dp_j*max_{k=0}^{j}a_k\)。我们在新加入一个位置后，只需要将弹出的部分从之前的\(sum\)中减去，再把新的区间的贡献加入。看起来非常简单。但是其中有些边界问题。
第一个问题是，我们如何处理开始的位置，第一个位置，我们给他设置的为dp[0]=1，因为，我们假设第一个位置加入后，我们应该是让dp[0]*a[1]，这个点是一定会加入的，因此我们设置初值的时候应当设置为dp[0]=1。
另外，为了计算的方便，我们将\(s_i\)的定义改变为，第i个位置对应的段，端内所有的\(dp\)值的和。
这样我们就解决了。
AC_code
#include<bits/stdc++.h>
#define ios ios::sync_with_stdio(false); cin.tie(0), cout.tie(0)
using namespace std;
using ll = long long;
const int N = 3e5 + 10,mod = 998244353;
int f[N],a[N],s1[N],s2[N];
int stk1[N],tt1,stk2[N],tt2;
int n;
int main()
{
ios;
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
ll sum1 = a[1],sum2 = a[1];
s1[1] = 1,s2[1] = 1;
stk1[++tt1] = stk2[++tt2] = 1;
f[0] = 1;
for(int i=2;i<=n;i++)
{
while(tt1&&a[i]>=a[stk1[tt1]])
{
s1[i] = (1ll*s1[i] + s1[stk1[tt1]])%mod;
sum1 = ((sum1 - 1ll*s1[stk1[tt1]]*a[stk1[tt1]]%mod)%mod + mod)%mod;
tt1--;
}
stk1[++tt1] = i;
s1[i] += f[i-1];
sum1 = (sum1 + 1l*s1[i]*a[i]%mod)%mod;
while(tt2&&a[i]<=a[stk2[tt2]])
{
s2[i] = (1ll*s2[i] + s2[stk2[tt2]])%mod;
sum2 = ((sum2 - 1ll*s2[stk2[tt2]]*a[stk2[tt2]]%mod)%mod + mod)%mod;
tt2--;
}
stk2[++tt2] = i;
s2[i] += f[i-1];
sum2 = (sum2 + 1l*s2[i]*a[i]%mod)%mod;
f[i] = ((sum1 - sum2)%mod + mod)%mod;
}
cout<<f[n]<<'\n';
}
F. Closest Pair
题目大意
- 给定 \(n(2 \le n \le 3\times 10^5)\) 个二元组 \((x_i,w_i)\)，其中 \(|x_i|\le 10^9\)，\(1\le w_i \le 10^9\)。
- 输入中二元组按照 \(x_i\) 严格递增排序给出。
- 给出 \(q(1\le q \le 3\times 10^5)\) 次询问，每次询问给出 \(l,r(1\le l<r \le n)\)，你需要输出：
分析
这里，用到了两个比较有趣的算法。
我们先来一步步分析。
我们来看这个式子，\(|x_i-x_j|*(w_i+w_j)\)，可以发现如果两个位置i,j之间，有比\(w_i,w_j\)还小的数的话，那么这一对点一定不会成为我们的目标答案。这点是很好推导出来了，因此我们的合法答案一定是，\(max(w_i,w_j)>min_{k=i+1}^{j-1}w_k\)的，即两点之间的权值一定比两者权值大。我们可以发现这就是类似于山峰的形式。因此我们不难想到，可以利用单调栈去计算得出所有合法的答案。
我们维护一个递增的单调栈，当将一个点入栈时，我们可以发现，所有的被弹出的点，都可以与入栈的该点成为合法点对，最后剩余的栈顶也可以与该点构成合法点对。这个算法很妙。这样操作完，我们发现，我们的点对数量也就是\(O(n)\)的。
然后，我们的问题就变为了，在所有的合法点对中，找到最小的了。这个问题就类似于之前做过的一道题目，CF522D Closest Equals，这题是要求所有相同的点构成的点对中距离最小的点对。
这个问题还是蛮经典的了，我们考虑使用线段树离线去做。
我们将所有的点对按右端点从大到小排序，或者不排序，直接开一个数组去存储，离线怎么做都行啦。这里我们采用第二种方法，我们反向枚举，枚举到一个点时，将该点是左端点的所有合法点对的权值，在右端点修改。然后将以该点为左端点的询问全部进行了。就结束啦。
AC_code
#include<bits/stdc++.h>
#define ios ios::sync_with_stdio(false); cin.tie(0), cout.tie(0)
using namespace std;
using ll = long long;
const int N = 3e5 + 10;
const ll inf = 8e18;
struct Node
{
int l,r;
ll mx,mi;
}tr[N<<2];
ll n,q,w[N],len;
void pushup(int u)
{
tr[u].mi = min(tr[u<<1].mi,tr[u<<1|1].mi);
tr[u].mx = max(tr[u<<1].mx,tr[u<<1|1].mx);
}
void build(int u,int l,int r)
{
tr[u] = {l,r,0,inf};
if(l==r) return ;
int mid = l + r >> 1;
build(u<<1,l,mid),build(u<<1|1,mid+1,r);
}
void modify(int u,int x,ll v)
{
if(tr[u].l==tr[u].r)
{
tr[u].mi = min(tr[u].mi,v);
tr[u].mx = max(tr[u].mx,v);
return ;
}
int mid = tr[u].l + tr[u].r >> 1;
if(x<=mid) modify(u<<1,x,v);
else modify(u<<1|1,x,v);
pushup(u);
}
ll querymin(int u,int l,int r)
{
if(tr[u].l>r||tr[u].r<l) return inf;
if(l<=tr[u].l&&tr[u].r<=r) return tr[u].mi;
return min(querymin(u<<1,l,r),querymin(u<<1|1,l,r));
}
ll querymax(int u,int l,int r)
{
if(tr[u].l>r||tr[u].r<l) return 0;
if(l<=tr[u].l&&tr[u].r<=r) return tr[u].mx;
return max(querymax(u<<1,l,r),querymax(u<<1|1,l,r));
}
struct node
{
int r;
ll v;
};
vector<node> Seg[N],Que[N];
ll ans[N],x[N];
int stk[N],tt;
int main()
{
ios;
cin>>n>>q;
for(int i=1;i<=n;i++) cin>>x[i]>>w[i];
for(int i=1;i<=n;i++)
{
while(tt&&w[stk[tt]]>=w[i])
{
int t = stk[tt];
Seg[t].push_back({i,(w[i] + w[t])*(x[i] - x[t])});
tt--;
}
if(tt)
{
int t = stk[tt];
Seg[t].push_back({i,(w[i] + w[t])*(x[i] - x[t])});
}
stk[++tt] = i;
}
for(int i=1;i<=q;i++)
{
int l,r;cin>>l>>r;
Que[l].push_back({r,i});
}
build(1,1,n);
modify(1,n,inf);
for(int i=n-1;i;i--)
{
for(auto st:Seg[i])
{
int r = st.r;
ll v = st.v;
modify(1,r,v);
}
for(auto st:Que[i])
{
int l = i,r = st.r,id = st.v;
ans[id] = querymin(1,l,r);
}
}
for(int i=1;i<=q;i++) cout<<ans[i]<<'\n';
return 0;
}
Souvenirs
题目大意
- 给出 \(n\) 以及一个长为 \(n\) 的序列 \(a\)。
- 给出 \(m\)，接下来 \(m\) 组询问。
- 每组询问给出一个 \(l,r\)，你需要求出，对于 \(i,j \in [l,r]\)，且满足 \(i \neq j\)，\(|a_i-a_j|\) 的最小值。
- \(1 \leq n \leq 10^5\)，\(1 \leq m \leq 3\times 10^5\)，\(0 \leq a_i \leq 10^9\)。
分析
给一个区间，让我们维护区间内值的差最小。第一眼看过去就是想能不能用主席树呢？但是权值又太大了，而且建起来之后，好像不能很好的让我们找到一个区间内的所有值的距离。但是这样划定一个范围，找区间内符合某些性质的点对，也是我们经常碰见的了。
我们考虑将询问离线，枚举右端点，这里我们只考虑\(j<i,a_j>a_i\)的答案，因为将\(a_i\)的值域反转后再做一遍就可以得到所有答案。我们维护的就是目标的值\(|a_j-a_i|\)，然后求以当前右端点为结尾的询问，设该区间为[l,r]，查询[1,l]的后缀最小值。我们想计算右端点的贡献所有，那肯定可以去找所有的满足\(j<i,a_j>a_i\)。但是这时间复杂度我们是不可以接受的，我们要想办法优化。
考虑对于当前的位置\(j\)，想让下一次找到的位置\(j'\)能更新答案，其必须满足\(a_{j'}-a_i<a_j-a_{j'}\)，因为位置\(j'\)更新过位置\(j\)，要更新后缀最小值，那就必须满足这个式子。移项后我们可以得到\(a_{j'}-a_i<\frac{1}{2}(a_j-a_i)\)，也就是说新的位置\(j'\)必须的权值必须满足\(\frac{a_i+a_j}{2}<a_{j'}<a_i\)。这样每次我们查询的值都减半，设值域为\(V\)，则时间复杂度为\(O(logV)\)。
还是满难想的。
AC_code
#include<bits/stdc++.h>
#define ios ios::sync_with_stdio(false); cin.tie(0), cout.tie(0)
using namespace std;
const int N = 3e5 + 10,inf = 0x3f3f3f3f;
typedef pair<int,int> pii;
struct Node
{
int l,r;
int mx;
}tr[N*33];
int n,m,cnt,root;
int a[N],ans[N],t[N];
vector<pii> que[N];
void add(int x,int k)
{
while(x)
{
t[x] = min(t[x],k);
x -= x & -x;
}
}
int querymin(int x)
{
int res = inf;
while(x<=n)
{
res = min(res,t[x]);
x += x & -x;
}
return res;
}
void pushup(int u)
{
tr[u].mx = max(tr[tr[u].l].mx,tr[tr[u].r].mx);
}
void modify(int &u,int l,int r,int x,int k)
{
if(!u) u = ++cnt;
if(l==r)
{
tr[u].mx = max(tr[u].mx,k);
return ;
}
int mid = l + r >> 1;
if(x<=mid) modify(tr[u].l,l,mid,x,k);
else modify(tr[u].r,mid+1,r,x,k);
pushup(u);
}
int query(int u,int l,int r,int x,int y)
{
if(l>y||r<x) return 0;
if(!u) return 0;
if(x<=l&&r<=y) return tr[u].mx;
int mid = l + r >> 1;
return max(query(tr[u].l,l,mid,x,y),query(tr[u].r,mid+1,r,x,y));
}
void clear()
{
for(int i=1;i<=n;i++) t[i] = inf;
for(int i=1;i<=cnt;i++) tr[i].l = tr[i].r = tr[i].mx = 0;
root = cnt = 0;
}
void solve()
{
clear();
for(int i=1;i<=n;i++)
{
int pos = query(root,0,inf,a[i],inf);
while(pos)
{
add(pos,a[pos] - a[i]);
pos = query(root,0,inf,a[i],(a[i] + a[pos])/2 - (~(a[i]+a[pos])&1));
}
modify(root,0,inf,a[i],i);
for(auto it:que[i])
ans[it.second] = min(ans[it.second],querymin(it.first));
}
}
int main()
{
ios;
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
cin>>m;
for(int i=1;i<=m;i++)
{
int l,r;cin>>l>>r;
ans[i] = inf;
que[r].push_back({l,i});
}
solve();
for(int i=1;i<=n;i++) a[i] = inf - a[i];
solve();
for(int i=1;i<=m;i++) cout<<ans[i]<<'\n';
return 0;
}