#百鬼夜行 http://163.23.148.103/problem/c003 TLE 請問我的方法有甚麼錯誤

1 messages · Page 1 of 1 (latest)

elfin salmon
# 
#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); 
    int t;
    cin>>t;
    while(t--){
        int n,m,e;
        vector<int> mst;
        cin>>n>>m>>e;
        int limit_l=m-e,limit_r=m+e,ans=0;
        mst.push_back(0);
        for(int i=0,sum=0,t;i<n;i++){
            cin>>t;
            sum+=t;
            int temp=sum;
            ans+=(upper_bound(mst.begin(),mst.end(),temp-limit_l)-mst.begin())-(lower_bound(mst.begin(),mst.end(),temp-limit_r)-mst.begin());
            mst.push_back(temp);
            sort(mst.begin(),mst.end());
        }
        cout<<ans<<"\n";
    }
}```
elfin salmon
#

時間複雜度應該是O(t*nlog(n))

dense epoch
#

mst一直推東西進去然後排序這樣是n^2logn吧

elfin salmon
#

mst 是vector推東西進去是O(1)
然後排序nlog(n)

#

所以應該還是O(t*nlog(n))

dense epoch
#

但你n次都在排序

elfin salmon
#

對吼

#

所以這個寫法不行嗎

#

還是有地方可以優化

dense epoch
#

直接弄BIT可以做一樣的事

elfin salmon
#

BIT會省下排序的時間
那我要怎麼知道有幾個是符合範圍的
如果用BIT窮舉時間複雜度會比較好嗎?
我對BIT不熟@@

dense epoch
#

我剛沒看題目，你可以先弄好前綴和然後做n次二分搜

elfin salmon
#

然後做n次二分搜是什麼意思

#

這樣不會多解嗎

dense epoch
#

然後要先離散化

dense epoch
#

max跟min都做一次就好

elfin salmon
#

我消化一下

dense epoch
#

我發現二分搜的解是爛的因為他的a_i會<0 (

elfin salmon
#

對

#

所以是代表只能用BIT的意思嗎

dense epoch
#

我現在是只有想到這個

elfin salmon
#

好thx

#

我嘗試看看BIT

#

ok

# 
#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); 
    int t;
    cin>>t;
    while(t--){
        int n,m,e;
        multiset<int> mst;
        vector<int> v;
        cin>>n>>m>>e;
        int limit_l=m-e,limit_r=m+e,ans=0;
        mst.insert(0);
        v.push_back(0);
        for(int i=0,t;i<n;i++){
            cin>>t;
            v.push_back(t+v.back());
            int temp=v.back();
            ans+=(distance(mst.begin(),mst.upper_bound(temp-limit_l)) - distance(mst.begin(),mst.lower_bound(temp-limit_r)));
            mst.insert(temp);
        }
        cout<<ans<<"\n";
    }
}```
順便提一下我第一次用multiset也是超時
#

這個的時間複雜度也是t*n^2logn嗎

dense epoch
#

感覺是log n

#

不知道為什麼TLE

#

過了

# 

int bit[100005];

void upd(int now){
    while(now<=100000) bit[now]++,now+=now&-now;
}

int val(int now){
    int iu=0;
    while(now>=1) iu+=bit[now],now-=now&-now;
    return iu;
}

void solve()
{
    int n,m,e;
    cin>>n>>m>>e;
    rep(i,n) bit[i]=0;
    int a[n+1];
    rep(i,n) cin>>a[i];
    int pre[n+1]={0};
    rep(i,n) pre[i]=pre[i-1]+a[i];
    vector<int>tt;
    rep(i,n) tt.pb(pre[i]);
    unisort(tt);
    int re[n+5];
    int mx1=-lar;
    
    rep(i,n){
        int gg=pre[i];
        pre[i]=lower_bound(tt.begin(),tt.end(),pre[i])-tt.begin()+1;
        re[pre[i]]=gg;
        mx1=max(mx1,pre[i]);
    }
    re[mx1+1]=lar;
    int ans=0;
    rep(i,n){
        int l=1,r=mx1+1;
        int mx=m+e,mn=m-e;
        while(l<r){
            int mid=l+r>>1;
            if(re[mid]>=re[pre[i]]-mx) r=mid;
            else l=mid+1;
        }
        int t1=l;
        l=1,r=mx1+1;
        while(l<r){
            int mid=l+r>>1;
            if(re[mid]>re[pre[i]]-mn) r=mid;
            else l=mid+1;
        }
        
        int t2=l;
        t2--,t1--;
        if(re[pre[i]]<=mx&&re[pre[i]]>=mn) ans++;
        if(t2==0||re[t2]<re[pre[i]]-mx){
            upd(pre[i]);
            continue;
        }
        else{
            ans+=val(t2)-val(t1);
            upd(pre[i]);
        }
    }
    cout<<ans<<"\n";
}

signed main()
{
    IO
    int t;
    cin>>t;
    while(t--)
    solve();
    return 0;
}
shrewd delta
#

這題看起來也可以分治

pure fossil
#

請問分治的部分要怎麼弄呢 我想到的方法都還是要排序

shrewd delta
#

分治搭配 merge sort

#

沒辦法直接二分搜是因為沒有單調性

#

但一邊分治一邊 merge sort 就可以了

elfin salmon
shrewd delta
#

沒用過那個函數，不知道他的時間複雜度，可能要去文件查一下（？
但應該是吧

elfin salmon
#

okok

#

thx

dense epoch
elfin salmon
#

那超時原因就是他了

#

看來multiset要知道idx不容易啊

dense epoch
# 
#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); 
    int t;
    cin>>t;
    while(t--){
        int n,m,e;
        multiset<int> mst;
        vector<int> v;
        cin>>n>>m>>e;
        int limit_l=m-e,limit_r=m+e,ans=0;
        mst.insert(0);
        v.push_back(0);
        for(int i=0,t;i<n;i++){
            cin>>t;
            v.push_back(t+v.back());
            int temp=v.back();
            auto k1=mst.upper_bound(temp-limit_l),k2=mst.lower_bound(temp-limit_r);
            ans+=distance(k2 , k1);
            mst.insert(temp);
        }
        cout<<ans<<"\n";
    }
}

我改成這樣就AC了

elfin salmon
#

太神啦

#

這樣的複雜度跟BIT會差很多嗎

dense epoch
#

所以我不知道為什麼你那樣寫會不行(

#

我iterator不熟

dense epoch