牛客多校第三场 G Removing Stones（分治+线段树）

题意：

给你n个数，问你有多少个长度不小于2的连续子序列，使得其中最大元素不大于所有元素和的一半

题解：

分治+线段树

线段树维护最大值的位置，每次分治找就找这个最大值，然后看最大值在哪个序列是可行的

怎么看最大值所在的序列是否可行呢？

我们用一个前缀和维护区间和

\[ max<=\frac{1}{2}(sum[r]-sum[l])\\ 2*max-(sum[r]-sum[l])<=0\\ \]

这个最大值在这一段区间内都有可能出现

为了得到总的方案数

我们在当前区间内枚举靠近最大值出现的位置pos的那一段，然后二分右\左端点，即可得到一段最小的区间[i,t]或者[t,i]可以满足区间内最大元素不大于所有元素和的一半的条件，然后计数就加上容斥后的r-t+1或者t-l+1这一段即可

代码：

/** *　　　　　　　　┏┓　　 　┏┓ * 　　　　　　　┏┛┗━━━━━━━┛┗━━━┓ * 　　　　　　　┃　　　　　　　┃ 　 * 　　　　　　　┃　　　━　　 　┃ * 　　　　　　　┃　＞　　　＜　┃ * 　　　　　　　┃　　　　　　　┃ * 　　　　　　　┃...　⌒　... 　┃ * 　　　　　　　┃　　　　　　　┃ * 　　　　　　　┗━┓　　　┏━┛ * 　　　　　　　　　┃　　　┃　Code is far away from bug with the animal protecting　　　　　　　　　　 * 　　　　　　　　　┃　　　┃   神兽保佑,代码无bug * 　　　　　　　　　┃　　　┃　　　　　　　　　　　 * 　　　　　　　　　┃　　　┃  　　　　　　 * 　　　　　　　　　┃　　　┃ * 　　　　　　　　　┃　　　┃　　　　　　　　　　　 * 　　　　　　　　　┃　　　┗━━━┓ * 　　　　　　　　　┃　　　　　　　┣┓ * 　　　　　　　　　┃　　　　　　　┏┛ * 　　　　　　　　　┗┓┓┏━┳┓┏┛ * 　　　　　　　　　　┃┫┫　┃┫┫ * 　　　　　　　　　　┗┻┛　┗┻┛ */// warm heart, wagging tail,and a smile just for you!////                            _ooOoo_//                           o8888888o//                           88" . "88//                           (| -_- |)//                           O\  =  /O//                        ____/`---'\____//                      .'  \|     |//  `.//                     /  \|||  :  |||//  \//                    /  _||||| -:- |||||-  \//                    |   | \  -  /// |   |//                    | \_|  ''\---/''  |   |//                    \  .-\__  `-`  ___/-. ///                  ___`. .'  /--.--\  `. . __//               ."" '<  `.___\_<|>_/___.'  >'"".//              | | :  `- \`.;`\ _ /`;.`/ - ` : | |//              \  \ `-.   \_ __\ /__ _/   .-` /  ///         ======`-.____`-.___\_____/___.-`____.-'======//                            `=---='//        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^//                     佛祖保佑      永无BUG#include 
    
     #include 
     #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               using namespace std;typedef long long LL;typedef pair
               
                 pii;typedef unsigned long long uLL;#define ls rt<<1#define rs rt<<1|1#define lson l,mid,rt<<1#define rson mid+1,r,rt<<1|1#define bug printf("*********\n")#define FIN freopen("input.txt","r",stdin);#define FON freopen("output.txt","w+",stdout);#define IO ios::sync_with_stdio(false),cin.tie(0)#define debug1(x) cout<<"["<<#x<<" "<<(x)<<"]\n"#define debug2(x,y) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<"]\n"#define debug3(x,y,z) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<" "<<#z<<" "<
                
                 <<"]\n"const int maxn = 3e5 + 5;const int INF = 0x3f3f3f3f;const int mod = 1e9 + 7;const double Pi = acos(-1);LL gcd(LL a, LL b) { return b ? gcd(b, a % b) : a;}LL lcm(LL a, LL b) { return a / gcd(a, b) * b;}double dpow(double a, LL b) { double ans = 1.0; while(b) { if(b % 2)ans = ans * a; a = a * a; b /= 2; } return ans;}LL quick_pow(LL x, LL y) { LL ans = 1; while(y) { if(y & 1) { ans = ans * x % mod; } x = x * x % mod; y >>= 1; } return ans;}pii Max[maxn << 2];LL sum[maxn];int a[maxn];void push_up(int rt) { Max[rt] = max(Max[ls], Max[rs]);}void build(int l, int r, int rt) { if(l == r) { Max[rt] = make_pair(a[l], l); return; } int mid = (l + r) >> 1; build(lson); build(rson); push_up(rt);}pii query(int L, int R, int l, int r, int rt) { if(L <= l && r <= R) { return Max[rt]; } int mid = (l + r) >> 1; pii ans = make_pair(0, 0); if(L <= mid) ans = max(ans, query(L, R, lson)); if(R > mid) ans = max(ans, query(L, R, rson)); return ans;}//二分最短区间大于后缀int find1(int l, int r, LL x) { int L = l, R = r + 1, res = l - 1; while (L <= R) { int mid = (L + R) >> 1; if (sum[r] - sum[mid - 1] >= x) { L = mid + 1; res = mid; } else R = mid - 1; } return res;}int find2(int l, int r, LL x) { int L = l - 1, R = r, res = r + 1; while (L <= R) { int mid = (L + R) >> 1; if (sum[mid] - sum[l - 1] >= x) { R = mid - 1; res = mid; } else L = mid + 1; } return res;}LL ans = 0;int n;void solve(int l, int r) { if(l == r) return; int mid = query(l, r, 1, n, 1).second; if(l < mid) solve(l, mid - 1); if(r > mid) solve(mid + 1, r); if(mid - l < r - mid) { for(int i = l; i <= mid; i++) { int t = find2(mid + 1, r, 2 * a[mid] - (sum[mid] - sum[i - 1])); ans += r - t + 1; } } else { for(int i = mid; i <= r; i++) { int t = find1(l, mid - 1, 2 * a[mid] - (sum[i] - sum[mid - 1])); ans += t - l + 1; } }}int main() {#ifndef ONLINE_JUDGE FIN#endif int T; scanf("%d", &T); while(T--) { scanf("%d", &n); sum[0] = 0; ans = 0; for(int i = 1; i <= n; i++) { scanf("%d", &a[i]); sum[i] = sum[i - 1] + a[i]; } build(1, n, 1); solve(1, n); printf("%lld\n", ans); } return 0;}

转载于:https://www.cnblogs.com/buerdepepeqi/p/11324366.html

你可能感兴趣的文章