Minieye杯第十五届华中科技大学程序设计邀请赛 C.Massive

太过爱你忘了你带给我的痛 2021-09-19 01:32 225阅读 0赞

首先我们可以很轻松的想到把做一个前缀和，枚举左端点，然后查询在合法区间内有多少个满足条件的右端点，因为数据结构太菜，比赛时先想了一下分块，但复杂度不太对，大概只能 O ( l o g n ) O(logn) O(logn)的查询,感觉不太可能，以为是什么NB的我不会的数据结构，然后就自闭了。  
**题解**  
首先我们把合法的前缀和离散化之后插到树状数组里面，实际上我们要维护的是一个前缀和的后缀和，在枚举的过程中，当左端点加一时 ，对应右端点的可能位置区间向右移了一位，我们加上那个后面的前缀和，同理，减去已经不再合法的前缀和即可（保证每次查询时我们的查询区间都是合法的）。直接枚举统计答案即可。

#include <bits/stdc++.h>
    using namespace std;
    #define rep(i,a,n) for (int i=a;i<n;i++)
    #define per(i,a,n) for (int i=n-1;i>=a;i--)
    #define pb push_back
    #define mp make_pair
    #define all(x) (x).begin(),(x).end()
    #define fi first
    #define se second
    #define SZ(x) ((int)(x).size())
    typedef vector<int> VI;
    typedef long long ll;
    typedef pair<int,int> PII;
    const ll mod=1000000007;
    ll powmod(ll a,ll b) { ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){ if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
    ll gcd(ll a,ll b) {  return b?gcd(b,a%b):a;}
    
    const int maxn = 1e6 + 100;
    
    ll a[maxn];
    ll sum[maxn];
    int n,l,r;
    ll s;
    
    struct Bit
    { 
        vector<int> a;
        int sz;
        void init(int n)
        { 
            sz=n;
            for(int i=1;i<=n+5;i++)
                a.push_back(0);
        }
        int lowbit(int x)
        { 
            return x&(-x);
        }
        int query(int x)
        { 
            int ans = 0;
            for(;x < sz;x+=lowbit(x))ans+=a[x];
            return ans;
        }
        void update(int x,int v)
        { 
            for(;x;x-=lowbit(x))
                a[x]+=v;
        }
    } bit;
    
    vector<ll> v;
    
    int getid(ll x)
    { 
    	return lower_bound(v.begin(),v.end(),x) - v.begin() + 1;
    }
    
    int main(int argc, char const *argv[])
    { 
    	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    	cin >> n >> l >> r >> s;
    	bit.init(2 * maxn);
    	rep(i,1,n+1) cin >> a[i];
    	rep(i,1,n+1) sum[i] = sum[i-1] + a[i];
    	rep(i,1,n+1) v.pb(sum[i]);
    	sort(all(v));
    	v.erase(unique(v.begin(),v.end()),v.end());
    
    	ll ans = 0;
        if(l>n)
        { 
            cout << 0 << endl;
            return 0;
        }
    	rep(i,l,min(n,r)+1) bit.update(getid(sum[i]),1);
        // rep(i,l,min(n,r)+1) cout << bit.query(getid(sum[i])) << endl;
    	rep(i,1,n+1)
    	{ 
    		if(i + l - 1 > n) break;
    		ans += bit.query(getid(s+sum[i-1]));
    // cout << getid(s+sum[i-1]) << endl;
    // cout << i << " " << ans << endl;
    		bit.update(getid(sum[i+l-1]),-1);
    		if(i + r <= n)
    		bit.update(getid(sum[i+r]),1);
    	}
    	cout << ans << endl;
    	return 0;
    }