結果

問題 No.1270 Range Arrange Query
ユーザー mugen_1337mugen_1337
提出日時 2020-10-24 00:09:10
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 6,351 bytes
コンパイル時間 2,926 ms
コンパイル使用メモリ 224,868 KB
実行使用メモリ 8,832 KB
最終ジャッジ日時 2024-07-21 14:06:09
合計ジャッジ時間 11,290 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 1 ms
5,376 KB
testcase_03 AC 3 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 4 ms
5,376 KB
testcase_06 TLE -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
権限があれば一括ダウンロードができます
コンパイルメッセージ
In lambda function,
    inlined from 'main()::<lambda(int)>' at main.cpp:218:14,
    inlined from 'constexpr _Res std::__invoke_impl(__invoke_other, _Fn&&, _Args&& ...) [with _Res = void; _Fn = main()::<lambda(int)>&; _Args = {int}]' at /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/invoke.h:61:36,
    inlined from 'constexpr std::enable_if_t<is_invocable_r_v<_Res, _Callable, _Args ...>, _Res> std::__invoke_r(_Callable&&, _Args&& ...) [with _Res = void; _Callable = main()::<lambda(int)>&; _Args = {int}]' at /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/invoke.h:111:28,
    inlined from 'static _Res std::_Function_handler<_Res(_ArgTypes ...), _Functor>::_M_invoke(const std::_Any_data&, _ArgTypes&& ...) [with _Res = void; _Functor = main()::<lambda(int)>; _ArgTypes = {int}]' at /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/std_function.h:290:30:
main.cpp:188:10: warning: 'u' may be used uninitialized [-Wmaybe-uninitialized]
  188 |         k=u;
      |         ~^~
main.cpp: In static member function 'static _Res std::_Function_handler<_Res(_ArgTypes ...), _Functor>::_M_invoke(const std::_Any_data&, _ArgTypes&& ...) [with _Res = void; _Functor = main()::<lambda(int)>; _ArgTypes = {int}]':
main.cpp:185:13: note: 'u' was declared here
  185 |         int u;
      |             ^
In lambda function,
    inlined from 'main()::<lambda(int)>' at main.cpp:204:14,
    inlined from 'constexpr _Res std::__invoke_impl(__invoke_other, _Fn&&, _Args&& ...) [with _Res = void; _Fn = main()::<lambda(int)>&; _Args = {int}]' at /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/invoke.h:61:36,
    inlined from 'constexpr std::enable_if_t<is_invocable_r_v<_Res, _Callable, _Args ...>, _Res> std::__invoke_r(_Callable&&, _Args&& ...) [with _Res = void; _Callable = main()::<lambda(int)>&; _Args = {int}]' at /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/invoke.h:111:28,
    inlined from 'sta

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
#define ALL(x) begin(x),end(x)
#define rep(i,n) for(int i=0;i<(n);i++)
#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl;
#define mod 1000000007
using ll=long long;
const int INF=1000000000;
const ll LINF=1001002003004005006ll;
int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
// ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return true;}return false;}

struct IOSetup{
    IOSetup(){
        cin.tie(0);
        ios::sync_with_stdio(0);
        cout<<fixed<<setprecision(12);
    }
} iosetup;
 
template<typename T>
ostream &operator<<(ostream &os,const vector<T>&v){
    for(int i=0;i<(int)v.size();i++) os<<v[i]<<(i+1==(int)v.size()?"":" ");
    return os;
}
template<typename T>
istream &operator>>(istream &is,vector<T>&v){
    for(T &x:v)is>>x;
    return is;
}

struct Mo{
    using F=function<void(int)>;
    int n,idx,ql,qr;
    vector<pair<int,int>> query;
    vector<int> ord;
    // [l,r) 
    // add_left  : l-1を足す, add_right : rを足す
    // erase_left: lを消す,  erase_right: r-1を消す
    F add_left,add_right,erase_left,erase_right;
 
    Mo(int n,F add_left,F add_right,F erase_left,F erase_right):
    n(n),idx(0),ql(0),qr(0),
    add_left(add_left),add_right(add_right),erase_left(erase_left),erase_right(erase_right)
    {}
 
    void add(int l,int r){
        query.emplace_back(l,r);
    }
 
    void build(){
        int q=(int)query.size();
        int bs=n/min(n,int(sqrt(q)));
        // 左端のブロックでソート
        // 左端のブロックが同じなら右端でソート
        ord.resize(q);
        iota(begin(ord),end(ord),0);
        sort(begin(ord),end(ord),[&](int a,int b){
            int al=query[a].first/bs,bl=query[b].first/bs;
            if(al!=bl) return al<bl;
            // 偶奇で始点を左右に振ると動きに無駄がない
            if(al&1) return query[a].second>query[b].second;
            return query[a].second<query[b].second;
        });
    }
 
    // 1個クエリを進め，処理したクエリのindexを返す
    // processが終わってから結果を格納すること
    // ans[process()]=res;とかはヤバイので注意．実装がよくない
    int process(){
        if(idx>=(int)ord.size()) return -1;
        int now=ord[idx++];
        while(ql>query[now].first)  add_left(--ql);
        while(qr<query[now].second) add_right(qr++);
        while(ql<query[now].first)  erase_left(ql++);
        while(qr>query[now].second) erase_right(--qr);
        return now;
    }
};

template<typename Monoid>
struct SegmentTree{
    using F=function<Monoid(Monoid,Monoid)>;
    int sz;
    vector<Monoid> seg;
    const F f;
    const Monoid gen;
    SegmentTree(int n,const F f,const Monoid &gen):f(f),gen(gen){
        sz=1;
        while(sz<n)sz<<=1;
        seg.assign(2*sz,gen);
    }
    void set(int k,const Monoid &x){
        seg[k+sz]=x;
    }
    void build(){
        for(int k=sz-1;k>0;k--) seg[k]=f(seg[2*k],seg[2*k+1]);
    }
    void update(int k,const Monoid &x){
        k+=sz;
        seg[k]=x;
        while(k>>=1) seg[k]=f(seg[2*k],seg[2*k+1]);
    }
   // [a,b)
    Monoid query(int a,int b){
        Monoid L=gen,R=gen;
        for(a+=sz,b+=sz;a<b;a>>=1,b>>=1){
            if(a&1) L=f(L,seg[a++]);
            if(b&1) R=f(seg[--b],R);
        }
        return f(L,R);
    }
    Monoid operator[](const int &k)const {
       return seg[k+sz];
    }
};

template<typename T>
struct BinaryIndexedTree{
   vector<T> data;
   BinaryIndexedTree()=default;
   BinaryIndexedTree(int sz):data(sz+1,0){}
   BinaryIndexedTree(const vector<T> &a):data(a.size()+1,0){
       for(int i=0;i<(int)a.size();i++)data[i+1]=a[i];
       for(int i=1;i<(int)data.size();i++){
           int j=i+(i&-i);
           if(j<(int)data.size()) data[j]+=data[i];
       }
   }
   void add(int k,const T &x){for(++k;k<(int)data.size();k+=(k&-k)) data[k]+=x;}
   // sum [0,k)
   T sum(int k){
       T ret=T();
       for(;k>0;k-=(k&-k))ret+=data[k];
       return ret;
   }
   // sum [l,r)
   T query(int l,int r){
       return sum(r)-sum(l);
   }
   T operator[](const int &k){return query(k,k+1);}
   // sum[0,i)>=xとなる最小のi
   int lower_bound(T x){
       int r=1,i=0;
       while(r<(int)data.size())r<<=1;
       for(;r>0;r>>=1)if(i+r<(int)data.size() and data[i+r]<x){
           x-=data[i+r];i+=r;
       }
       return i+1;
   }
};



signed main(){
    int n,q;cin>>n>>q;
    vector<int> a(n);
    rep(i,n){
        cin>>a[i];
        a[i]--;
    }

    auto segfunc=[&](int lhs,int rhs){
        return lhs+rhs;
    };
    SegmentTree<int> seg_l(n,segfunc,0),seg_r(n,segfunc,0);
    seg_l.build();
    seg_r.build();
    ll inv=0;
    // build_r
    vector<int> cnt(n,0);
    {
        for(auto &x:a){
            cnt[x]++;
            inv+=seg_r.query(x+1,n);
            seg_r.update(x,cnt[x]);
        }
    }

    // 仕切りの位置をずらす
    int k=0;// 仕切り
    auto shake=[&](){
        int u;
        int d=INF;
        rep(i,n)if(chmin(d,seg_r.query(0,i)+seg_l.query(i+1,n))) u=i;
        k=u;
    };


    auto add_l=[&](int x){
        inv-=seg_l.query(a[x]+1,n);
        inv-=seg_r.query(0,a[x]);

        seg_l.update(a[x],seg_l[a[x]]-1);
        shake();
    };
    auto add_r=[&](int x){
        inv-=seg_l.query(a[x]+1,n);
        inv-=seg_r.query(0,a[x]);

        seg_r.update(a[x],seg_r[a[x]]-1);
        shake();
    };
    auto erase_l=[&](int x){
        inv+=seg_l.query(a[x]+1,n);
        inv+=seg_r.query(0,a[x]);

        seg_l.update(a[x],seg_l[a[x]]+1);
        shake();
    };
    auto erase_r=[&](int x){
        inv+=seg_l.query(a[x]+1,n);
        inv+=seg_r.query(0,a[x]);

        seg_r.update(a[x],seg_r[a[x]]+1);
        shake();
    };

    Mo mo(n,add_l,add_r,erase_l,erase_r);
    vector<ll> ans(q);
    vector<int> l(q),r(q);
    rep(i,q){
        cin>>l[i]>>r[i];l[i]--;
        mo.add(l[i],r[i]);
    }
    mo.build();

    rep(i,q){
        int j=mo.process();
        ans[j]=ll(seg_l.query(k+1,n)+seg_r.query(0,k))*(r[j]-l[j]);
        ans[j]+=inv;
        // cout<<l[i]<<" ~ "<<r[i]<<" : "<<k<<" ("<<inv<<")"<<endl;
    }
    for(auto &x:ans) cout<<x<<endl;
    return 0;
}
0