#include <bits/stdc++.h>
using namespace std;
const int nx=3e5+5;
#define ll long long
ll n, q, v[nx], t, l, r;
struct gap
{
ll type, g;
gap(ll type=0, ll g=0): type(type), g(g){}
friend bool operator==(const gap &lhs, const gap &rhs) {return lhs.type||rhs.type||lhs.g==rhs.g;}
friend bool operator!=(const gap &lhs, const gap &rhs) {return !(lhs==rhs);}
};
gap opposite(gap o) { return gap(o.type, -o.g);}
struct segtree
{
struct node
{
gap gapl, gapr;
ll type, mx, mxl, mxr, vl, vr, sz;
node(ll x=0, ll type=0): type(type), mx(1), mxl(1), mxr(1), vl(x), vr(x), gapl(gap(1)), gapr(gap(1)), sz(1) {}
friend node operator+(const node &lhs, const node &rhs)
{
if (lhs.type) return rhs;
if (rhs.type) return lhs;
node res=node();
gap gapl=gap(0, rhs.vl-lhs.vr), gapr=gap(0, lhs.vr-rhs.vl);
res.vl=lhs.vl;
res.vr=rhs.vr;
res.sz=lhs.sz+rhs.sz;
res.gapl=lhs.gapl.type?gapl:lhs.gapl;
res.gapr=rhs.gapr.type?gapr:rhs.gapr;
if (lhs.mxl!=lhs.sz||lhs.gapl!=gapl) res.mxl=lhs.mxl;
else res.mxl=(gapl==rhs.gapl)?lhs.mxl+rhs.mxl:lhs.mxl+1;
if (rhs.mxr!=rhs.sz||rhs.gapr!=gapr) res.mxr=rhs.mxr;
else res.mxr=(gapr==lhs.gapr)?lhs.mxr+rhs.mxr:rhs.mxr+1;
res.mx=max(res.mx, res.mx);
if (opposite(lhs.gapr)==gapl) res.mx=max(res.mx, lhs.mxr+1);
if (rhs.gapl==gapl) res.mx=max(res.mx, rhs.mxl+1);
if (opposite(lhs.gapr)==gapl&&gapl==rhs.gapl) res.mx=max(res.mx, lhs.mxr+rhs.mxl);
return res;
}
} d[4*nx];
void build(int l, int r, int i)
{
if (l==r) return void(d[i]=node(v[l], 0));
int md=(l+r)/2;
build(l, md, 2*i);
build(md+1, r, 2*i+1);
d[i]=d[2*i]+d[2*i+1];
}
node query(int l, int r, int i, int ql, int qr)
{
if (qr<l||r<ql) return node(0, 1);
if (ql<=l&&r<=qr) return d[i];
int md=(l+r)/2;
return query(l, md, 2*i, ql, qr)+query(md+1, r, 2*i+1, ql, qr);
}
} s;
int main()
{
cin.tie(NULL)->sync_with_stdio(false);
cin>>n>>q;
for (int i=1; i<=n; i++) cin>>v[i];
s.build(1, n, 1);
while (q--)
{
cin>>t;
if (t==1) continue;
if (t==2) continue;
if (t==3)
{
cin>>l>>r;
cout<<s.query(1, n, 1, l, r).mx<<'\n';
}
}
}
Compilation message
Progression.cpp: In constructor 'segtree::node::node(long long int, long long int)':
Progression.cpp:24:36: warning: 'segtree::node::vr' will be initialized after [-Wreorder]
24 | ll type, mx, mxl, mxr, vl, vr, sz;
| ^~
Progression.cpp:23:13: warning: 'gap segtree::node::gapl' [-Wreorder]
23 | gap gapl, gapr;
| ^~~~
Progression.cpp:25:9: warning: when initialized here [-Wreorder]
25 | node(ll x=0, ll type=0): type(type), mx(1), mxl(1), mxr(1), vl(x), vr(x), gapl(gap(1)), gapr(gap(1)), sz(1) {}
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
83 ms |
110416 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
105304 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
234 ms |
113144 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
89 ms |
110584 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
234 ms |
113144 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
83 ms |
110416 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
