牛客练习赛66 E 骚区间 线段树+扫描线
题目链接:https://ac.nowcoder.com/acm/contest/6112/E?&headNav=acm
题目大意:
#pragma GCC optimize(3,"Ofast","inline") #include <bits/stdc++.h> #define LL long long #define mid (l+r>>1) using namespace std; const int N=1e6+7; LL INF=0; inline int read(){ int 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; } struct SegTree { LL T[N<<2], pos[N<<2]; inline void pushup(int o) { if(T[o<<1]<T[o<<1|1]){ T[o]=T[o<<1]; pos[o]=pos[o<<1]; } else{ T[o]=T[o<<1|1]; pos[o]=pos[o<<1|1]; } } void BT(int o, int l, int r){ if(l==r){ T[o]=INF; pos[o]=l; return ; } BT(o<<1, l, mid); BT(o<<1|1, mid+1, r); pushup(o); } void add(int o,int l,int r,int pos,LL v){//修改 T[o]=v if(l==r) { T[o]=v; return; } pos<=mid ? add(o<<1,l,mid,pos,v) : add(o<<1|1,mid+1,r,pos,v); pushup(o); } pair<int, int> query(int o,int l,int r,int ql,int qr){//查询区间最大值 if(l>qr||r<ql) return {INF, INF}; if(l>=ql&&r<=qr) return {T[o], pos[o]}; return min(query(o<<1,l,mid,ql,qr),query(o<<1|1,mid+1,r,ql,qr)); } }T; LL s[1000005]; void add(LL x,LL z) {for (LL i=x;i<=N;i+=(i&(-i))) s[i]+=z;} LL ask(LL x) {LL ans=0;for (LL i=x;i>0;i-=(i&(-i))) ans+=s[i];return ans;} LL ask(LL x, LL y){return ask(y)-ask(x-1);} int a[1000050], l[1000050], r[1000050]; vector<pair<int, int> > v1[1000050], v2[1000050]; int main() { int n; scanf("%d", &n); INF=n+1; T.BT(1, 1, n); for(int i=1; i<=n; i++){ a[i]=read(); T.add(1, 1, n, a[i], i); } /*预处理l, r*/ for(int i=1; i<=n; i++){ pair<int , int> pos1=T.query(1, 1, n, 1, a[i]-1); l[i]=pos1.first; T.add(1, 1, n, pos1.second, INF); pair<int , int> pos2=T.query(1, 1, n, 1, a[i]-1); r[i]=pos2.first-1; T.add(1, 1, n, pos1.second, pos1.first); T.add(1, 1, n, a[i], INF); } INF=0; for(int i=1; i<=n; i++){ T.add(1, 1, n, a[i], -i); } /*预处理L, R*/ for(int i=n; i>=1; i--){ pair<int , int> pos1=T.query(1, 1, n, a[i]+1, n); int R=-pos1.first; T.add(1, 1, n, pos1.second, INF); pair<int , int> pos2=T.query(1, 1, n, a[i]+1, n); int L=-pos2.first+1; T.add(1, 1, n, pos1.second, pos1.first); T.add(1, 1, n, a[i], INF);for (int i = 1; i <= n; i++) rev[sa[i]] = i; set<int> S; for (int i = 1; i <= n; i++) { int id = rev[i]; S.insert(id); auto a = S.upper_bound(id); if (a == S.end()) continue; Inc[*a].push_back(id); a++; if (a != S.end()) Dec[(*a) - 1].push_back(id); } S.clear(); for (int i = n; i >= 1; i--) { int id = rev[i]; S.insert(-id); auto a = S.upper_bound(-id); if (a == S.end()) continue; qr[id] -= (*a); a++; if (a == S.end()) ql[id] = 1; else ql[id] -= (*a) - 1; } if(L<=R){ v1[L].push_back({1, i}); v2[R].push_back({-1, i}); } } LL ANS=0; for(int i=1; i<=n; i++){ for(auto x: v1[i]){//加入 add(x.second, x.first); } if(l[i]<=r[i]){ ANS+=ask(l[i], r[i]); } for(auto x: v2[i]){//删除 add(x.second, x.first); } } printf("%lld\n", ANS); return 0; } /* set预处理 for (int i = 1; i <= n; i++) rev[sa[i]] = i; set<int> S; for (int i = 1; i <= n; i++) { int id = rev[i]; S.insert(id); auto a = S.upper_bound(id); if (a == S.end()) continue; Inc[*a].push_back(id); a++; if (a != S.end()) Dec[(*a) - 1].push_back(id); } S.clear(); for (int i = n; i >= 1; i--) { int id = rev[i]; S.insert(-id); auto a = S.upper_bound(-id); if (a == S.end()) continue; qr[id] -= (*a); a++; if (a == S.end()) ql[id] = 1; else ql[id] -= (*a) - 1; } */