結果

問題 No.3078 Difference Sum Query
ユーザー nouka28
提出日時 2025-03-28 22:15:08
言語 C++17(clang)
(17.0.6 + boost 1.87.0)
結果
AC  
実行時間 1,966 ms / 2,000 ms
コード長 2,279 bytes
コンパイル時間 4,777 ms
コンパイル使用メモリ 191,948 KB
実行使用メモリ 12,340 KB
最終ジャッジ日時 2025-03-28 22:15:42
合計ジャッジ時間 29,892 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

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 ALL(x) (x).begin(),(x).end()
#define fi first
#define se second
struct fast_io{fast_io(){cin.tie(nullptr)->sync_with_stdio(false);}}_;
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);
            }
        }
    };
signed main(){
    #define int long long
    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);
    }
    vector<int> v=A;v.insert(v.end(),ALL(X));
    sort(ALL(v));v.erase(unique(ALL(v)),v.end());
    
    fenwick_tree<int> tr(v.size()),tr2(v.size());
    vector<int> idx(N);
    rep(i,N)idx[i]=lower_bound(ALL(v),A[i])-v.begin();
    auto xp=[&](int i){
        tr.add(idx[i],-1);
        tr2.add(idx[i],-A[i]);
    };
    auto xm=[&](int i){
        tr.add(idx[i],1);
        tr2.add(idx[i],A[i]);
    };
    auto yp=[&](int i){
        tr.add(idx[i],1);
        tr2.add(idx[i],A[i]);
    };
    auto ym=[&](int i){
        tr.add(idx[i],-1);
        tr2.add(idx[i],-A[i]);
    };
    vector<int> ans(Q);
    auto out=[&](int id){
        // cout<<"id : ";
        // tr.dump();
        int idx=lower_bound(ALL(v),X[id])-v.begin();
        ans[id]+=X[id]*tr.sum(0,idx)-tr2.sum(0,idx);
        ans[id]+=tr2.sum(idx,v.size())-X[id]*tr.sum(idx,v.size());
    };
    mo.solve(N,xp,xm,yp,ym,out);
    rep(i,Q)cout<<ans[i]<<"\n";
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0