結果

問題 No.3078 Difference Sum Query
ユーザー nouka28
提出日時 2025-03-28 22:03:55
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 8,645 bytes
コンパイル時間 7,193 ms
コンパイル使用メモリ 340,896 KB
実行使用メモリ 7,324 KB
最終ジャッジ日時 2025-03-28 22:04:13
合計ジャッジ時間 12,025 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 6 TLE * 1 -- * 19
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include<bits/stdc++.h>
using namespace std;
#include<atcoder/all>
using namespace atcoder;
using mint=atcoder::modint998244353;
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define rep(i,n) for(int i=0;i<(n);i++)
#define rng(i,l,r) for(int i=(l);i<(r);i++)
#define aint(x) (x).begin(),(x).end()
#define int long long
#define fi first
#define se second
struct fast_io{fast_io(){cin.tie(nullptr)->sync_with_stdio(false);}}_;
    //乱数系
random_device rnd; 
mt19937 mt(rnd());
const long long MT_MAX=1e18;
uniform_int_distribution<long long> rd(0,MT_MAX);
double randd(){
    return 1.0*rd(mt)/MT_MAX;
}
long long randint(long long a,long long b){
    // [a,b]の乱数を生成
    return a+rd(mt)%(b-a+1);
}
template<class T> T SortedMultiList_default_op(T a,T b){return max(a,b);}
template<class T> T SortedMultiList_default_e(){return 0;}
template<class T,T(*op)(T,T)/*=SortedMultiList_default_op<T>*/,T(*e)()/*=SortedMultiList_default_e<T>*/>
class SortedMultiList{
    struct Node{
        T key,acc;
        int priority,cnt;
        Node *l,*r;
        Node(T key,int priority):key(key),acc(key),priority(priority),cnt(1),l(nullptr),r(nullptr){}
    }*root=nullptr;
    using Tree=Node*;
    
    int cnt(Tree t){
        return t?t->cnt:0;
    }
    
    T acc(Tree t){
        return t?t->acc:e();
    }
    void update(Tree &t){
        if(t){
            t->cnt=1+cnt(t->l)+cnt(t->r);
            t->acc=op(op(acc(t->l),t->key),acc(t->r));
        }
    }
    void split(Tree t,T key,Tree &l,Tree &r){
        if(!t){
            l=r=nullptr;
        }else if(key<t->key){
            split(t->l,key,l,t->l),r=t;
        }else{
            split(t->r,key,t->r,r),l=t;
        }
        update(t);
    }
    void split_by_index(Tree t,int idx,Tree &l,Tree &r){
        if(!t){
            l=r=nullptr;
        }else if(cnt(t->l)>=idx){
            split_by_index(t->l,idx,l,t->l),r=t;
        }else{
            split_by_index(t->r,idx-cnt(t->l)-1,t->r,r),l=t;
        }
        update(t);
    }
    void merge(Tree &t,Tree l,Tree r){
        if(!l||!r){
            t=l?l:r;
        }else if(l->priority>r->priority){
            merge(l->r,l->r,r),t=l;
        }else{
            merge(r->l,l,r->l),t=r;
        }
        update(t);
    }
    void insert(Tree &t,Tree item){
        if(!t){
            t=item;
        }else if(item->priority>t->priority){
            split(t,item->key,item->l,item->r),t=item;
            update(t);
        }else{
            insert(item->key<t->key?t->l:t->r,item);
            update(t);
        }
    }
    void erase(Tree &t,T key){
        if(!t)return;
        if(t->key==key){
            merge(t,t->l,t->r);
            update(t);
        }else{
            erase(key<t->key?t->l:t->r,key);
            update(t);
        }
    }
    bool find(Tree &t,T key){
        if(!t){
            return false;
        }else if(t->key==key){
            return true;
        }else{
            return find(key<t->key?t->l:t->r,key);
        }
    }
    T index(Tree &t,int idx){
        int siz=(t->l?t->l->cnt:0);
        if(idx==siz){
            return t->key;
        }else if(idx<siz){
            return index(t->l,idx);
        }else{
            return index(t->r,idx-siz-1);
        }
    }
    int lower_bound(Tree &t,T key){
        if(!t)return 0;
        int siz=(t->l?t->l->cnt:0);
        if(t->key>=key){
            return lower_bound(t->l,key);
        }else{
            return siz+1+lower_bound(t->r,key);
        }
    }
    int upper_bound(Tree &t,T key){
        if(!t)return 0;
        int siz=(t->l?t->l->cnt:0);
        if(t->key>key){
            return upper_bound(t->l,key);
        }else{
            return siz+1+upper_bound(t->r,key);
        }
    }
    T prod(Tree t,int l,int r){
        Tree t1,t2,t3;
        split_by_index(t,l,t1,t2);
        split_by_index(t2,r-l,t2,t3);
        T res=acc(t2);
        merge(t2,t2,t3);
        merge(t,t1,t2);
        return res;
    }
    template<class F>
    int max_right(Tree t,const F &f,T product){
        if(!f(product))return 0;
        if(f(op(product,acc(t))))return cnt(t);
        int m=max_right(t->l,f,product);
        if(m<cnt(t->l))return m;
        product=op(product,acc(t->l));
        if(!f(op(product,t->key)))return cnt(t->l);
        product=op(product,t->key);
        return cnt(t->l)+1+max_right(t->r,f,product);
    }
    template<class F>
    int min_left(Tree t,const F &f,T product){
        if(!f(product))return cnt(t);
        if(f(op(product,acc(t))))return 0;
        int m=min_left(t->r,f,product);
        if(0<m)return cnt(t->l)+1+m;
        product=op(product,acc(t->r));
        if(!f(op(product,t->key)))return cnt(t->l)+1;
        product=op(product,t->key);
        return min_left(t->l,f,product);
    }
    void to_vector(Tree t,vector<T> &vec){
        if(!t)return;
        to_vector(t->l,vec);
        vec.push_back(t->key);
        to_vector(t->r,vec);
    };
    void dump(Tree t){
        if(!t)return;
        if(t->l){
            dump(t->l);cout<<" ";
        }
        cout<<t->key;
        if(t->r){
            cout<<" ";dump(t->r);
        }
    };
    public:
    void insert(T key){
        insert(root,new Node(key,randint(0,1LL<<63)));
    }
    void erase(T key){
        erase(root,key);
    }
    bool find(T key){
        return find(root,key);
    }
    T index(int idx){
        return index(root,idx);
    }
    T operator[](int idx){
        return index(root,idx);
    }
    int lower_bound(T key){
        return lower_bound(root,key);
    }
    int upper_bound(T key){
        return upper_bound(root,key);
    }
    int count(T key){
        return upper_bound(root,key)-lower_bound(root,key);
    }
    int size(){
        return (root?root->cnt:0);
    }
    T prod(int l,int r){
        return prod(root,l,r);
    }
    template<bool(*f)(T)>int max_right(int l){
        return max_right(l,[](T x){return f(x);});
    }
    template<class F>int max_right(int l,const F& f){
        assert(l<=cnt(root));
        T product=e();
        assert(f(product));
        Tree t1,t2;split_by_index(root,l,t1,t2);
        int res=l+max_right(t2,f,product);
        merge(root,t1,t2);
        return res;
        
    }
    template<bool (*f)(T)>int min_left(int r){
        return min_left(r,[](T x){return f(x);});
    }
    template<class F>int min_left(int r,const F& f){
        assert(r<=cnt(root));
        T product=e();
        assert(f(product));
        Tree t1,t2;split_by_index(root,r,t1,t2);
        int res=min_left(t1,f,product);
        merge(root,t1,t2);
        return res;
    }
    vector<T> to_vector(){
        vector<T> vec;to_vector(root,vec);
        return vec;
    }
    void dump(){
        dump(root);
        cout<<endl;
    }
    constexpr bool operator==(const SortedMultiList<T,op,e> &rhs)const noexcept{
        return to_vector()==rhs.to_vector();
    }
    constexpr bool operator!=(const SortedMultiList<T,op,e> &rhs)const noexcept{
        return to_vector()!=rhs.to_vector();
    }
};
struct Mo{
    private:
        struct Q{
            int x,y,id;
        };
        vector<Q> Queries;
    public:
        void add_query(int x,int y,int id){
            Queries.push_back({x,y,id});
        }
    
        /*
        prod [x,y) or [0,x),[0,y)
        */
        template<class XP,class XM,class YP,class YM,class O>
        void solve(const int n,const XP& x_plus,const XM& x_minus,const YP& y_plus,const YM& y_minus,const O& out){
            int q=(int)Queries.size();
            int bs=n/min<int>(n,sqrt(q));
            sort(Queries.begin(),Queries.end(),[&](Q q1,Q q2)->bool {
                if(q1.x/bs<q2.x/bs)return 1;
                if(q1.x/bs==q2.x/bs){
                    if(q1.x/bs&1)return q1.y<q2.y;
                    else return q1.y>q2.y;
                }
                return 0;
            });
            int x=0,y=0;
            for(auto&&query:Queries){
                while(y<query.y)y_plus(y++);
                while(x>query.x)x_minus(--x);
                while(y>query.y)y_minus(--y);
                while(x<query.x)x_plus(x++);
                
                out(query.id);
            }
        }
    };
int op(int a,int b){return a+b;}
int e(){return 0;}
signed main(){
    int N,Q;cin>>N>>Q;
    vector<int> A(N);for(auto&&e:A)cin>>e;
    Mo mo;
    vector<int> X(Q);
    rep(i,Q){
        int l,r;cin>>l>>r;cin>>X[i];l--;
        mo.add_query(l,r,i);
    }
    SortedMultiList<int,op,e> tr;
    auto xp=[&](int i){
        tr.erase(A[i]);
    };
    auto xm=[&](int i){
        tr.insert(A[i]);
    };
    auto yp=[&](int i){
        tr.insert(A[i]);
    };
    auto ym=[&](int i){
        tr.erase(A[i]);
    };
    vector<int> ans(Q);
    auto out=[&](int id){
        // cout<<"id : ";
        // tr.dump();
        int idx=tr.lower_bound(X[id]);
        ans[id]+=X[id]*idx-tr.prod(0,idx);
        ans[id]+=tr.prod(idx,tr.size())-X[id]*(tr.size()-idx);
    };
    mo.solve(N,xp,xm,yp,ym,out);
    rep(i,Q)cout<<ans[i]<<"\n";
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0