1007B逆序对（二维数点问题 窗口星星）

http://cplusoj.com/d/senior/p/SS241007B

显然这题是一个二维数点问题，我们要求在确定 $[l,r]$ 下 $i$ 个数的最大值：

• $l<i<r$
• $a_r<i<a_l$

考场上想了各种扫描线，cdq，kdtree，可持久化，树套树都想不起这个套路是啥，这其实是一个经典的套路，窗口的星星

矩阵和点的相互转化

而在此题，我们也就看每个 $i$ 能作用哪些 $[l,r]$，我们把这个覆盖区域变成一个矩形，那么就是求最多矩形覆盖的有多少，这个可以就是裸的二维数点了

而为了让它张成一个矩形，我们发现只需要维护前后的上升/下降序列作为关键点即可

#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
 #define debug(...) fprintf(stdout, ##__VA_ARGS__)
 #define debag(...) fprintf(stderr, ##__VA_ARGS__)
#else
 #define debug(...) void(0)
 #define debag(...) void(0)
#endif
#define int long long
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;}
#define Z(x) (x)*(x)
#define pb push_back
#define fi first
#define se second
//#define M
//#define mo
#define N 1000010
int n, m, i, j, k, T;
int a[N], x, y, s1, s2; 
int lmx[N], rmx[N], lst, ans; 

int find_L(int i) {
int l = 1, r = lmx[i], mid; 
while(l < r) {
mid = (l + r) >> 1; 
if(a[lmx[mid]] >= a[i]) r = mid; 
else l = mid + 1; 
}
return l; 
}

int find_R(int i) {
int l = rmx[i], r = n, mid; 
while(l < r) {
mid = (l + r + 1) >> 1; 
if(a[rmx[mid]] <= a[i]) l = mid; 
else r = mid - 1; 
}
return r; 
}

namespace Scan {
struct Segment_tree {
#define ls (k << 1)
#define rs (k << 1 | 1) 
#define mid ((l + r) >> 1)
int tag[N << 2], mx[N << 2]; 
void push_down(int k) {
tag[ls] += tag[k]; tag[rs] += tag[k]; mx[ls] += tag[k]; mx[rs] += tag[k]; 
tag[k] = 0; 
}
void add(int k, int l, int r, int x, int y, int z) {
if(l >= x && r <= y) return tag[k] += z, mx[k] += z, void(); 
push_down(k); 
if(x <= mid) add(ls, l, mid, x, y, z); 
if(y >= mid + 1) add(rs, mid + 1, r, x, y, z); 
mx[k] = max(mx[ls], mx[rs]); 
}
#undef ls
#undef rs
#undef mid
}Seg;
struct node { int l, r, v; };
vector<node>G[N]; 
void insert(int lx, int ly, int rx, int ry) {
//debug("Polygon\n%lld %lld\n%lld %lld\n%lld %lld\n%lld %lld\n", 
//lx, rx, lx, ry + 1, ly + 1, ry + 1, ly + 1, rx); 
debug("%lld %lld %lld %lld\n", lx, ly, rx, ry); 
G[rx].pb({lx, ly, 1}); G[ry + 1].pb({lx, ly, -1}); 
}
int run() {
int i, ans = 0; 
for(i = 1; i <= n; ++i) {
for(auto t : G[i]) {
Seg.add(1, 1, n, t.l, t.r, t.v); 
}
ans = max(ans, Seg.mx[1]); 
}
return ans; 
}
}

signed main()
{
  freopen("inverse.in", "r", stdin);
  freopen("inverse.out", "w", stdout);
//srand(time(NULL));
//T = read();
//while(T--) {
//
//}
n = read(); 
for(i = 1; i <= n; ++i) a[i] = read(); 
for(i = 1, lst = 0; i <= n; ++i) {
if(a[i] > lst) lst = a[i], lmx[i] = i; else lmx[i] = lmx[i - 1]; 
}
for(i = n, lst = 1e9; i >= 1; --i) {
if(a[i] < lst) lst = a[i], rmx[i] = i; else rmx[i] = rmx[i + 1]; 
}
for(i = 1; i <= n; ++i) debug("%lld ", lmx[i]); debug("\n"); 
for(i = 1; i <= n; ++i) debug("%lld ", rmx[i]); debug("\n"); 
for(i = 1; i <= n; ++i) {
int L = find_L(i), R = find_R(i); 
Scan :: insert(L, lmx[i], rmx[i], R); 
}
ans = Scan :: run(); 
printf("%lld", 2 * ans - 3); 
return 0;
}

原文地址：https://blog.csdn.net/zhangtingxiqwq/article/details/142741239

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！