CF484E Sign on Fence
文章目录
【注意】最后更新于 April 21, 2020，文中内容可能已过时，请谨慎使用。
题目描述
给你一个数列 $a_{1..n}$，进行 $m$ 次询问，每次询问给出一个区间 $[l, r]$ 及参数 $w$，询问 $\max_{i = l}^{r-w+1}\{\min_{j=i}^{i+w-1}\{a_j\}\}$。
数列长度和询问次数 $10^5$。
简要做法
O((n+m)log^2n) 做法
二分答案，记当前二分的值为 $x$，定义 $b_i=\begin{cases}1&a_i\ge x\\-n&a_i<x\end{cases}$，那么答案不小于 $x$ 当且仅当 $b_{l..r}$ 的最大子段和不小于 $w$。
最大子段和可以用线段树维护，记录每个区间的最大子段和，最大前缀，最大后缀，以及总和即可。
然后用主席树或 整体二分 就能在 $O((n+m)\log^2n)$ 的时间复杂度内解决这道题。
（其实我自己没写主席树做法，听说别人都写的主席树，口胡了一下，感觉应该和整体二分做法差不多..）
O((n+m)(logn+logm)) 做法
首先用单调栈求出每个点作为最小值最远能向左延伸到 $p_i$，向右延伸到 $q_i$。
那么，我们将每个 $[p_i, q_i]$ 看作一条权值为 $a_i$ 的线段，每次询问就是求与 $[l, r]$ 的交不小于 $w$ 的线段里最大的权值。
$[p_i, q_i]$ 和 $[l, r]$ 相交有两种情况：
-
$p_i<l$
此时若 $[p_i, q_i]$ 和 $[l, r]$ 的交不小于 $w$，则 $[l, l+w-1]$ 必然是一个合法的交。而在这种情况下，$\min_{j=l}^{l+w-1}\{a_j\}$ 必然不小于 $a_i$（因为 $a_i$ 是 $[p_i, q_i]$ 内的最小值，而 $[p_i, q_i]$ 包含 $[l, l+w-1]$），所以只需考虑 $[l, l+w-1]$ 便不劣于这种情况下的任一线段。 -
$p_i\ge l$
这种情况下，$[p_i, q_i]$ 和 $[l, r]$ 的交不小于 $w$ 等价于 $l\le p_i\le r-w+1$ 且 $q_i-p_i+1\ge w$。只要对线段和询问分别按长度和 $w$ 从大到小排序，双指针枚举就可以满足 $q_i-p_i+1\ge w$，而 $\max_{l\le p_i\le r-w+1}a_i$ 可以用线段树维护（枚举到线段时在 $p_i$ 处对 $a_i$ 取 max，枚举到询问时在 $[l, r-w+1]$ 这个区间上求 max）。
然后把这两种情况的答案取 max，就做完了。
参考代码
代码中的线段树用了 板子。整体二分这份代码还用了 CF 板子。
整体二分 O((n+m)log^2n)
#ifndef OUUAN
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#endif
#include<bits/stdc++.h>
template<typename valueType,typename modType>struct SegmentTreeNode{public:std::size_t id;long long left,right;valueType val;modType mod;};template<typename valueType,typename modType,bool elementModificationOnly=false>class SegmentTree{public:SegmentTree()=default;SegmentTree(const std::vector<valueType>&_initValue,std::function<valueType(const valueType&,const valueType&)>_merge,std::function<void(SegmentTreeNode<valueType,modType>&,const modType&)>_update,long long _startPoint=1,const valueType&_valueZero=valueType(),const modType&_modZero=modType()){init(_initValue,_merge,_update,_startPoint,_valueZero,_modZero);}void init(const std::vector<valueType>&_initValue,std::function<valueType(const valueType&,const valueType&)>_merge,std::function<void(SegmentTreeNode<valueType,modType>&,const modType&)>_update,long long _startPoint=1,const valueType&_valueZero=valueType(),const modType&_modZero=modType()){assert(_startPoint>=LLONG_MIN/2);assert(_startPoint<=LLONG_MAX/2-(long long)_initValue.size());leftRange=_startPoint;rightRange=_startPoint+_initValue.size();m_init(_initValue,_merge,_update,_valueZero,_modZero);}void modify(long long l,long long r,const modType&mod){assert(!elementModificationOnly);modify(1,leftRange,rightRange,l,r,mod);}void modify(long long p,const modType&mod){assert(p<LLONG_MAX);modify(1,leftRange,rightRange,p,p+1,mod);}valueType query(long long l,long long r){return query(1,leftRange,rightRange,l,r);}valueType query(long long p){return query(p,p+1);}private:void pushup(std::size_t cur){nodes[cur].val=merge(nodes[cur<<1].val,nodes[cur<<1|1].val);}void pushdown(std::size_t cur){update(nodes[cur<<1],nodes[cur].mod);update(nodes[cur<<1|1],nodes[cur].mod);nodes[cur].mod=modZero;}void build(std::size_t cur,long long l,long long r,const std::vector<valueType>&initValue){nodes[cur].id=cur;nodes[cur].left=l;nodes[cur].right=r;nodes[cur].mod=modZero;if(l==r-1)nodes[cur].val=initValue[l-leftRange];else{build(cur<<1,l,(l+r)>>1,initValue);build(cur<<1|1,(l+r)>>1,r,initValue);pushup(cur);}}void m_init(const std::vector<valueType>&_initValue,std::function<valueType(const valueType&,const valueType&)>_merge,std::function<void(SegmentTreeNode<valueType,modType>&,const modType&)>_update,const valueType&_valueZero,const modType&_modZero){merge=_merge;update=_update;valueZero=_valueZero;modZero=_modZero;nodes.resize((rightRange-leftRange)<<2);build(1,leftRange,rightRange,_initValue);}void modify(std::size_t cur,long long l,long long r,long long L,long long R,const modType&mod){if(l>=R||r<=L)return;if(L<=l&&r<=R)update(nodes[cur],mod);else{if(!elementModificationOnly)pushdown(cur);modify(cur<<1,l,(l+r)>>1,L,R,mod);modify(cur<<1|1,(l+r)>>1,r,L,R,mod);pushup(cur);}}valueType query(std::size_t cur,long long l,long long r,long long L,long long R){if(l>=R||r<=L)return valueZero;if(L<=l&&r<=R)return nodes[cur].val;if(!elementModificationOnly)pushdown(cur);return merge(query(cur<<1,l,(l+r)>>1,L,R),query(cur<<1|1,(l+r)>>1,r,L,R));}std::function<valueType(const valueType&,const valueType&)>merge;std::function<void(SegmentTreeNode<valueType,modType>&,const modType&)>update;std::vector<SegmentTreeNode<valueType,modType>>nodes;long long leftRange=0,rightRange=0;valueType valueZero;modType modZero;};
// #define int ll
// #define FAST_IOSTREAM 1
#define For(i,l,r)for(int i=(l),i##end=(r);i<=i##end;++i)
#define FOR(i,r,l)for(int i=(r),i##end=(l);i>=i##end;--i)
#define SON(i,u)for(int i=head[u];i;i=nxt[i])
#define BE(x)(x).begin(),(x).end()
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define pq priority_queue
#define min minOfDifferentTypes
#define max maxOfDifferentTypes
#define y1 why_is_there_a_function_called_y1
using namespace std;typedef long long ll;typedef pair<int,int>pii;typedef vector<int>vi;typedef vector<vi> vvi;typedef vvi v2i;typedef vector<vvi>v3i;typedef vector<v3i>v4i;typedef vector<bool>vb;typedef vector<vb>vvb;typedef vvb v2b;typedef vector<vvb>v3b;typedef vector<v3b>v4b;typedef vector<pii>vpii;typedef vector<vpii>vvpii;typedef vvpii v2pii;typedef vector<vvpii>v3pii;typedef vector<v3pii>v4pii;typedef long double ld;typedef vector<ld>vd;typedef vector<vd>vvd;typedef vvd v2d;typedef vector<v2d>v3d;typedef vector<v3d>v4d;const ld inf=1e121;const ld eps=1e-10;mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());int randint(int l,int r){int out=rng()%(r-l+1)+l;return out>=l?out:out+r-l+1;}template<typename A,typename B>string to_string(pair<A,B>p);template<typename A,typename B,typename C>string to_string(tuple<A,B,C>p);template<typename A,typename B,typename C,typename D>string to_string(tuple<A,B,C,D>p);string to_string(const string&s){return '"'+s+'"';}string to_string(const char*s){return to_string((string)s);}string to_string(bool b){return(b?"true":"false");}string to_string(vector<bool>v){bool first=true;string res="{";for(int i=0;i<static_cast<int>(v.size());i++){if(!first){res+=",";}first=false;res+=to_string(v[i]);}res+="}";return res;}template<size_t N>string to_string(bitset<N>v){string res="";for(size_t i=0;i<N;i++){res+=static_cast<char>('0'+v[i]);}return res;}template<typename A>string to_string(A v){bool first=true;string res="{";for(const auto&x:v){if(!first){res+=",";}first=false;res+=to_string(x);}res+="}";return res;}template<typename A,typename B>string to_string(pair<A,B>p){return "("+to_string(p.first)+","+to_string(p.second)+")";}template<typename A,typename B,typename C>string to_string(tuple<A,B,C>p){return "("+to_string(get<0>(p))+","+to_string(get<1>(p))+","+to_string(get<2>(p))+")";}template<typename A,typename B,typename C,typename D>string to_string(tuple<A,B,C,D>p){return "("+to_string(get<0>(p))+","+to_string(get<1>(p))+","+to_string(get<2>(p))+","+to_string(get<3>(p))+")";}template<typename A,typename B,typename C,typename D,typename E>string to_string(tuple<A,B,C,D,E>p){return "("+to_string(get<0>(p))+","+to_string(get<1>(p))+","+to_string(get<2>(p))+","+to_string(get<3>(p))+","+to_string(get<4>(p))+")";}void debug_out(){cerr<<endl;}template<typename Head,typename...Tail>void debug_out(Head H,Tail...T){cerr<<" "<<to_string(H);debug_out(T...);}template<typename T>struct is_pair{static const bool value=false;};template<typename T,typename U>struct is_pair<std::pair<T,U>>{static const bool value=true;};
#ifdef OUUAN
#define debug(...)cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
#else
#define debug(...)42
#endif
#ifdef int
const int INF=0x3f3f3f3f3f3f3f3fll;
#else
const int INF=0x3f3f3f3f;
#endif
#ifdef FAST_IOSTREAM
#define br cout<<'\n'
#define sp cout<<' '
#define fl cout.flush()
ll read(){ll x;cin>>x;return x;}template<typename T>void read(T&x){cin>>x;}template<typename T>void write(const T&x){cout<<x;}
#else
#define br putchar('\n')
#define sp putchar(' ')
#define fl fflush(stdout)
template<typename T>typename enable_if<!is_integral<T>::value&&!is_pair<T>::value,void>::type read(T&x){cin>>x;}ll read(){char c;ll out=0,f=1;for(c=getchar();!isdigit(c)&&c!='-';c=getchar());if(c=='-'){f=-1;c=getchar();}for(;isdigit(c);c=getchar())out=(out<<3)+(out<<1)+c-'0';return out*f;}template<typename T>typename enable_if<is_integral<T>::value,T>::type read(T&x){char c;T f=1;x=0;for(c=getchar();!isdigit(c)&&c!='-';c=getchar());if(c=='-'){f=-1;c=getchar();}for(;isdigit(c);c=getchar())x=(x<<3)+(x<<1)+c-'0';return x*=f;}char read(char&x){for(x=getchar();isspace(x);x=getchar());return x;}double read(double&x){scanf("%lf",&x);return x;}ld read(ld&x){scanf("%Lf",&x);return x;}template<typename T>typename enable_if<!is_integral<T>::value&&!is_pair<T>::value,void>::type write(const T&x){cout<<x;}template<typename T>typename enable_if<is_integral<T>::value,void>::type write(const T&x){if(x<0){putchar('-');write(-x);return;}if(x>9)write(x/10);putchar(x%10+'0');}void write(const char&x){putchar(x);}void write(const double&x){printf("%.10lf",x);}void write(const ld&x){printf("%.10Lf",x);}
#endif
template<typename T>typename enable_if<is_pair<T>::value,void>::type read(T&x){read(x.fi);read(x.se);}template<typename T>typename enable_if<is_pair<T>::value,void>::type write(const T&x){write(x.fi);sp;write(x.se);}template<typename T,typename...Args>void read(T&x,Args&...args){read(x);read(args...);}template<typename OutputIt,typename=typename enable_if<is_same<output_iterator_tag,typename iterator_traits<OutputIt>::iterator_category>::value||(is_base_of<forward_iterator_tag,typename iterator_traits<OutputIt>::iterator_category>::value&&!is_const<OutputIt>::value)>::type>void read(OutputIt __first,OutputIt __last){for(;__first!=__last;++__first)read(*__first);}template<typename InputIt,typename=typename enable_if<is_base_of<input_iterator_tag,typename iterator_traits<InputIt>::iterator_category>::value>::type>void wts(InputIt __first,InputIt __last){bool isFirst=true;for(;__first!=__last;++__first){if(isFirst)isFirst=false;else sp;write(*__first);}br;}template<typename InputIt,typename=typename enable_if<is_base_of<input_iterator_tag,typename iterator_traits<InputIt>::iterator_category>::value>::type>void wtb(InputIt __first,InputIt __last){for(;__first!=__last;++__first){write(*__first);br;}}template<typename T>void wts(const T&x){write(x);sp;}template<typename T>void wtb(const T&x){write(x);br;}template<typename T>void wte(const T&x){write(x);exit(0);}template<typename T,typename...Args>void wts(const T&x,Args...args){wts(x);wts(args...);}template<typename T,typename...Args>void wtb(const T&x,Args...args){wts(x);wtb(args...);}template<typename T,typename...Args>void wte(const T&x,Args...args){wts(x);wte(args...);}template<typename T1,typename T2>inline bool up(T1&x,const T2&y){return x<y?x=y,1:0;}template<typename T1,typename T2>inline bool dn(T1&x,const T2&y){return y<x?x=y,1:0;}template<typename T1,typename T2,typename T3>inline bool inRange(const T1&x,const T2&l,const T3&r){return!(x<l)&&!(r<x);}template<typename T1,typename T2>inline auto minOfDifferentTypes(const T1&x,const T2&y)->decltype(x<y?x:y){return x<y?x:y;}template<typename T1,typename T2>inline auto maxOfDifferentTypes(const T1&x,const T2&y)->decltype(x<y?y:x){return x<y?y:x;}template<typename T1,typename T2,typename T3>inline T1&madd(T1&x,const T2&y,const T3&modulo){return x=(ll)(x+y+modulo)%modulo;}template<typename T1,typename T2,typename T3>inline T1&mmul(T1&x,const T2&y,const T3&modulo){return x=(ll)x*y%modulo;}inline int modadd(int x,int y,int modulo){return(x+=y)>=modulo?x-modulo:x;}inline int isinf(int x){return x<INF?x:-1;}inline void yesno(bool x){wtb(x?"Yes":"No");}
/* ------------------------------------------------------------------------------------------------------------------- */
struct Modify
{
int p, x;
};
struct Query
{
int l, r, w, id;
};
struct Val
{
int ans, pre, suf, sum;
};
signed main()
{
#ifdef FAST_IOSTREAM
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
#endif
int n = read();
vector<Modify> modify;
vi lsh;
For (i, 1, n)
{
int x = read();
lsh.pb(x);
modify.pb({i, x});
}
sort(BE(lsh));
lsh.resize(unique(BE(lsh)) - lsh.begin());
for (auto &m : modify) m.x = lower_bound(BE(lsh), m.x) - lsh.begin();
int k = read();
vector<Query> query;
For (i, 0, k - 1)
{
int l = read();
int r = read();
int w = read();
query.pb({l, r, w, i});
}
SegmentTree<Val, int, true> seg
(
vector<Val>(n, {0, 0, 0, -n}),
[n](const Val &x, const Val &y)
{
Val res;
res.ans = max(x.suf + y.pre, max(x.ans, y.ans));
res.pre = max(x.pre, x.sum + y.pre);
res.suf = max(y.suf, x.suf + y.sum);
res.sum = max(x.sum + y.sum, -n);
return res;
},
[](SegmentTreeNode<Val, int> &node, int x)
{
if (x == INF) return;
node.val.ans = node.val.pre = node.val.suf = max(0, x);
node.val.sum = x;
},
1,
{0, 0, 0, 0},
INF
);
vi ans(k);
function<void(vector<Modify> &, vector<Query> &, int, int)> solve = [&](vector<Modify> &ms, vector<Query> &qs, int l, int r)
{
if (qs.empty()) return;
if (l == r - 1)
{
for (auto q : qs)
{
ans[q.id] = lsh[l];
}
return;
}
vector<Modify> lm, rm;
int mid = (l + r) >> 1;
for (auto m : ms)
{
if (m.x >= mid)
{
seg.modify(m.p, 1);
rm.push_back(m);
}
else lm.push_back(m);
}
vector<Query> lq, rq;
for (auto q : qs)
{
if (seg.query(q.l, q.r + 1).ans >= q.w) rq.push_back(q);
else lq.push_back(q);
}
vector<Modify>().swap(ms);
vector<Query>().swap(qs);
solve(lm, lq, l, mid);
for (auto m : rm) seg.modify(m.p, -n);
solve(rm, rq, mid, r);
};
solve(modify, query, 0, lsh.size());
for (auto x : ans) wtb(x);
return 0;
}
O((n+m)(logn+logm))
#include <bits/stdc++.h>
template<typename valueType,typename modType>struct SegmentTreeNode{public:std::size_t id;long long left,right;valueType val;modType mod;};template<typename valueType,typename modType,bool elementModificationOnly=false>class SegmentTree{public:SegmentTree()=default;SegmentTree(const std::vector<valueType>&_initValue,std::function<valueType(const valueType&,const valueType&)>_merge,std::function<void(SegmentTreeNode<valueType,modType>&,const modType&)>_update,long long _startPoint=1,const valueType&_valueZero=valueType(),const modType&_modZero=modType()){init(_initValue,_merge,_update,_startPoint,_valueZero,_modZero);}void init(const std::vector<valueType>&_initValue,std::function<valueType(const valueType&,const valueType&)>_merge,std::function<void(SegmentTreeNode<valueType,modType>&,const modType&)>_update,long long _startPoint=1,const valueType&_valueZero=valueType(),const modType&_modZero=modType()){assert(_startPoint>=LLONG_MIN/2);assert(_startPoint<=LLONG_MAX/2-(long long)_initValue.size());leftRange=_startPoint;rightRange=_startPoint+_initValue.size();m_init(_initValue,_merge,_update,_valueZero,_modZero);}void modify(long long l,long long r,const modType&mod){assert(!elementModificationOnly);modify(1,leftRange,rightRange,l,r,mod);}void modify(long long p,const modType&mod){assert(p<LLONG_MAX);modify(1,leftRange,rightRange,p,p+1,mod);}valueType query(long long l,long long r){return query(1,leftRange,rightRange,l,r);}valueType query(long long p){return query(p,p+1);}private:void pushup(std::size_t cur){nodes[cur].val=merge(nodes[cur<<1].val,nodes[cur<<1|1].val);}void pushdown(std::size_t cur){update(nodes[cur<<1],nodes[cur].mod);update(nodes[cur<<1|1],nodes[cur].mod);nodes[cur].mod=modZero;}void build(std::size_t cur,long long l,long long r,const std::vector<valueType>&initValue){nodes[cur].id=cur;nodes[cur].left=l;nodes[cur].right=r;nodes[cur].mod=modZero;if(l==r-1)nodes[cur].val=initValue[l-leftRange];else{build(cur<<1,l,(l+r)>>1,initValue);build(cur<<1|1,(l+r)>>1,r,initValue);pushup(cur);}}void m_init(const std::vector<valueType>&_initValue,std::function<valueType(const valueType&,const valueType&)>_merge,std::function<void(SegmentTreeNode<valueType,modType>&,const modType&)>_update,const valueType&_valueZero,const modType&_modZero){merge=_merge;update=_update;valueZero=_valueZero;modZero=_modZero;nodes.resize((rightRange-leftRange)<<2);build(1,leftRange,rightRange,_initValue);}void modify(std::size_t cur,long long l,long long r,long long L,long long R,const modType&mod){if(l>=R||r<=L)return;if(L<=l&&r<=R)update(nodes[cur],mod);else{if(!elementModificationOnly)pushdown(cur);modify(cur<<1,l,(l+r)>>1,L,R,mod);modify(cur<<1|1,(l+r)>>1,r,L,R,mod);pushup(cur);}}valueType query(std::size_t cur,long long l,long long r,long long L,long long R){if(l>=R||r<=L)return valueZero;if(L<=l&&r<=R)return nodes[cur].val;if(!elementModificationOnly)pushdown(cur);return merge(query(cur<<1,l,(l+r)>>1,L,R),query(cur<<1|1,(l+r)>>1,r,L,R));}std::function<valueType(const valueType&,const valueType&)>merge;std::function<void(SegmentTreeNode<valueType,modType>&,const modType&)>update;std::vector<SegmentTreeNode<valueType,modType>>nodes;long long leftRange=0,rightRange=0;valueType valueZero;modType modZero;};
using namespace std;
int read()
{
int out = 0;
char c;
while (!isdigit(c = getchar()));
for (; isdigit(c); c = getchar()) out = out * 10 + c - '0';
return out;
}
typedef vector<int> vi;
const int INF = 1e9;
struct Query
{
int l, r, w, id;
bool operator<(const Query &b) const
{
return w > b.w;
}
};
int main()
{
int n = read();
vi a(n);
for (int i = 0; i < n; ++i) a[i] = read();
vi p(n), len(n);
stack<int> stk;
for (int i = 0; i < n; ++i)
{
while (stk.size() && a[stk.top()] >= a[i]) stk.pop();
if (stk.empty()) p[i] = 0;
else p[i] = stk.top() + 1;
stk.push(i);
}
stack<int>().swap(stk);
for (int i = n - 1; i >= 0; --i)
{
while (stk.size() && a[stk.top()] >= a[i]) stk.pop();
int r;
if (stk.empty()) r = n - 1;
else r = stk.top() - 1;
len[i] = r - p[i] + 1;
stk.push(i);
}
vi id(n);
for (int i = 0; i < n; ++i) id[i] = i;
sort(id.begin(), id.end(), [&](int x, int y) { return len[x] > len[y]; });
SegmentTree<int, bool, true> mn
(
a,
[](int x, int y) { return min(x, y); },
[](SegmentTreeNode<int, bool> &, bool) {},
1,
INF
);
int m = read();
vi ans(m);
vector<Query> query;
for (int i = 0; i < m; ++i)
{
int l = read();
int r = read();
int w = read();
query.push_back({l, r, w, i});
ans[i] = mn.query(l, l + w);
}
sort(query.begin(), query.end());
SegmentTree<int, int, true> mx
(
vi(n),
[](int x, int y) { return max(x, y); },
[](SegmentTreeNode<int, int> &node, int x)
{
node.val = max(node.val, x);
node.mod = max(node.mod, x);
}
);
auto it = id.begin();
for (auto t : query)
{
while (it != id.end() && len[*it] >= t.w)
{
mx.modify(p[*it] + 1, a[*it]);
++it;
}
ans[t.id] = max(ans[t.id], mx.query(t.l, t.r - t.w + 2));
}
for (auto x : ans) printf("%d\n", x);
return 0;
}
评论正在加载中...如果评论较长时间无法加载，你可以 搜索对应的 issue 或者 新建一个 issue 。