本文主要是介绍2653: middle，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
震惊，竟然一遍ac...
一眼扫过去并没有思路...
但是一般来说求区间第k小都是主席树，考虑这题是否能用主席树...发现对区间建主席树似乎并不好处理...
然后考虑枚举答案ans的话能否建主席树，显然对于一段区间，如果大于该数的数-小于该数的数 >= 0，则答案至少为ans
那么二分答案，对权值建树，一开始把所有节点标为1，表示所有数都至少大于第0个数，然后按权值大小依次更新，
显然把第i个数以下都标为-1，但是因为第i-1个数在处理i-1已经更新，所以其实只用更改第i个数即可...
然后统计区间最大左子段，右子段，以及权值和即可。
c++代码如下：
#include<bits/stdc++.h>
#define rep(i,x,y) for(register int i = x ; i <= y;++ i)
#define repd(i,x,y) for(register int i = x ; i >= y;-- i)
typedef long long ll;
using namespace std;
template<typename T>inline void read(T&x)
{x = 0;char c;int sign = 1;do { c = getchar(); if(c == '-') sign = -1; }while(!isdigit(c));do { x = x * 10 + c - '0'; c = getchar(); }while(isdigit(c));x *= sign;
}const int M = 2e7+500,N = 3e4+500,inf = 1e9+7;
int root[N],n,q,sz;
int ls[M],rs[M],lmax[M],rmax[M],num[M],val[M];
struct Str { int id,w; }A[N];
bool operator < (Str a,Str b) { return a.w < b.w; }void build(int&rt,int l,int r)
{rt = ++ sz;num[rt] = lmax[rt] = rmax[rt] = r - l + 1;if(l == r) return ;int mid = l + r >> 1;build(ls[rt],l,mid);build(rs[rt],mid + 1,r);
}void insert(int&rt1,int rt2,int l,int r,int x)
{rt1 = ++sz;num[rt1] = num[rt2] - 2;if(l == r){lmax[rt1] = rmax[rt1] = num[rt1];return;}ls[rt1] = ls[rt2]; rs[rt1] = rs[rt2];int mid = l + r>> 1; if(x <= mid) insert(ls[rt1],ls[rt2],l,mid,x);else insert(rs[rt1],rs[rt2],mid + 1,r,x);rmax[rt1] = max(rmax[rs[rt1]],num[rs[rt1]] + rmax[ls[rt1]]);lmax[rt1] = max(lmax[ls[rt1]],num[ls[rt1]] + lmax[rs[rt1]]);
}int query_num(int rt,int l,int r,int L,int R)
{if(l == L && r == R) return num[rt];int mid = l + r >> 1;if(R <= mid) return query_num(ls[rt],l,mid,L,R);if(L > mid) return query_num(rs[rt],mid + 1,r,L,R);return query_num(ls[rt],l,mid,L,mid) + query_num(rs[rt],mid+1,r,mid+1,R);
}int query_lmax(int rt,int l,int r,int L,int R)
{if(l == L && r == R) return lmax[rt];int mid = l + r >> 1;if(R <= mid) return query_lmax(ls[rt],l,mid,L,R);if(L > mid) return query_lmax(rs[rt],mid + 1,r,L,R);return max(query_num(ls[rt],l,mid,L,mid) + query_lmax(rs[rt],mid+1,r,mid+1,R),query_lmax(ls[rt],l,mid,L,mid));
}int query_rmax(int rt,int l,int r,int L,int R)
{if(l == L && r == R) return rmax[rt];int mid = l + r >> 1;if(R <= mid) return query_rmax(ls[rt],l,mid,L,R);if(L > mid) return query_rmax(rs[rt],mid + 1,r,L,R);return max(query_rmax(ls[rt],l,mid,L,mid) + query_num(rs[rt],mid+1,r,mid+1,R),query_rmax(rs[rt],mid + 1,r,mid + 1,R));
}int main()
{read(n);rep(i,1,n){read(A[i].w);A[i].id = i;}sort(A + 1,A + 1 + n);build(root[0],1,n);rep(i,1,n - 1)insert(root[i],root[i - 1],1,n,A[i].id);read(q);int a,b,c,d,ans = 0;while(q -- ){read(a); read(b); read(c); read(d);a = (a + ans) % n; b = (b + ans) % n;c = (c + ans) % n; d = (d + ans) % n;a++;b++,c++,d++;if(b < a) swap(a,b); if(c < a) swap(a,c);if(d < a) swap(a,d); if(c < b) swap(b,c);if(d < b) swap(b,d); if(d < c) swap(c,d);int l = 0,r = n - 1,mid;while(l <= r){mid = l + r >> 1;if((c - b > 1?query_num(root[mid],1,n,b + 1,c - 1) : 0) + query_rmax(root[mid],1,n,a,b) + query_lmax(root[mid],1,n,c,d) >= 0) ans = mid,l = mid + 1;else r = mid - 1;}printf("%d\n",(ans = A[ans + 1].w));}return 0;
}
这篇关于2653: middle的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
