競プロ復習 ABC174 F問題
https://atcoder.jp/contests/abc174/tasks/abc174_f
クオリ区間ごとの個数を求める問題。
・累積和を使う
この手の問題は、クオリをソートした順にみて行くといいです。
(前のクオリの結果が再利用できるため、高速化に繋がる)
今回はrを昇順ソートしました。
struct QUARR{
int l;
int r;
int index;
int type;
int ans;
bool operator<(QUARR q) const{
if(type==1){
if(q.r==r) return q.l>l;
return q.r>r;
}
else{
return q.index>index;
}
}
};答えはソート前で出力しないといけないため、戻す用のソートも定義しています。
rが小さい順に見ていき、玉の色の一番右を記録しておきます。
※
1 2 3 1 3 1
というc[i]に対してrをどんどん広げて、玉の色の一番右を記録
r=1 1->1
r=2 1->1 2->2
r=3 1->1 2->2 3->3
r=4 1->4 2->2 3->3
r=5 1->4 2->2 3->5
r=6 1->6 2->2 3->5
また、右端の玉の色が記録されている場所を1にするようなBIT列を考えます。
※1 2 3 1 3 1
r=1 100000
r=2 110000
r=3 111000
r=4 011100
r=5 010110
r=6 010011
このbit列に対して、[l,r]区間の答えを求める際、1の数を数えることで答えが求まるようになります。
(0の場所にある玉の色は、それより右にある1のどれかと同じになっているため)
また、累積和を用いることでO(1)で区間の和が求めそうです。
※1 2 3 1 3 1
r=1 111111
r=2 122222
r=3 123333
r=4 012333
r=5 011233
r=6 011123
[3,5]の場合、r=5の累積和を用いて3-1=2と答えが求まります。
・フェニック木で累積和を高速化
累積和の更新にオーダーがかかるため、まだTLE解です。
ただ、こういった累積和の更新を高速に行えるデータ構造があります。
https://ja.wikipedia.org/wiki/%E3%83%95%E3%82%A7%E3%83%8B%E3%83%83%E3%82%AF%E6%9C%A8
フェニック木(fenwick tree)です。(BITって呼ばれてるものと同じ？)
C++の標準ライブラリにないデータ構造なので、自前で準備する必要がありますが、実装は簡単にできます。
int ft_bit[NMAX];
void ft_add(int a,int w,int N){
for(int x=a;x<=N;x+=x&-x){
ft_bit[x]+=w;
}
}
int ft_sum(int a){
int ret=0;
for(int x=a;x>0;x-=x&-x){
ret+=ft_bit[x];
}
return ret;
}参考(http://hos.ac/slides/20140319_bit.pdf)
ft_addが累積和の更新です。[a,N]区間にwを加えます。
x&-xは、xを二進で見たときに一番下にある1が取れます。
ft_sumは累積和の算出です。[1,N]区間の累積和を求めます。
二進の一番下の1に1を足したり、引いたりしているためループは長くてもO(logN)で終わりそうです。
・提出コード
という訳で、以下提出コードです。
//#include<bits/stdc++.h> #include <iostream> #include <algorithm> #include <cmath> #include <vector> #include <queue> #include <set>
/* #include <boost/multiprecision/cpp_int.hpp> #include <boost/multiprecision/cpp_dec_float.hpp> #include <boost/rational.hpp>
namespace mp = boost::multiprecision;
using Real = mp::number<mp::cpp_dec_float<1024>>;
using Bint = mp::cpp_int;
*/
using namespace std; #define int long long #define REP(i,s,e) for((i)=(s);(i)<(e);(i)++) #define RREP(i,s,e) for((i)=((s)-1);(i)>=(e);(i)--) #define FOR(i,n) for((i)=(0);(i)<(n);(i)++) #define RFOR(i,n) for((i)=((n)-1);(i)>=(0);(i)--) #define MOD 1000000007 #define NMAX 500010
struct QUARR{
int l;
int r;
int index;
int type;
int ans;
bool operator<(QUARR q) const{
if(type==1){
if(q.r==r) return q.l>l;
return q.r>r;
}
else{
return q.index>index;
}
}
};
int ft_bit[NMAX];
void ft_add(int a,int w,int N){
for(int x=a;x<=N;x+=x&-x){
ft_bit[x]+=w;
}
}
int ft_sum(int a){
int ret=0;
for(int x=a;x>0;x-=x&-x){
ret+=ft_bit[x];
}
return ret;
}
signed main(){
QUARR qu[NMAX];
int last[NMAX];
int c[NMAX];
int N,Q;
cin>>N>>Q;
for(int i=1;i<=N;i++){
cin>>c[i];
last[i]=-1;
}
for(int i=1;i<=Q;i++){
int l,r;
cin>>l>>r;
qu[i].l=l;
qu[i].r=r;
qu[i].index=i;
qu[i].type=1;
qu[i].ans=0;
}
sort(qu+1,qu+Q+1);
for(int i=1;i<=qu[1].r;i++){
if(last[c[i]]==-1){
ft_add(i,1,N);
last[c[i]]=i;
}
else{
ft_add(last[c[i]],-1,N);
ft_add(i,1,N);
last[c[i]]=i;
}
}
qu[1].ans=ft_sum(qu[1].r)-ft_sum(qu[1].l-1);
qu[1].type=2;
for(int i=2;i<=Q;i++){
for(int j=qu[i-1].r+1;j<=qu[i].r;j++){
if(last[c[j]]==-1){
ft_add(j,1,N);
last[c[j]]=j;
}
else{
ft_add(last[c[j]],-1,N);
ft_add(j,1,N);
last[c[j]]=j;
}
}
qu[i].ans=ft_sum(qu[i].r)-ft_sum(qu[i].l-1);
qu[i].type=2;
}
sort(qu+1,qu+Q+1);
for(int i=1;i<=Q;i++){
cout<<qu[i].ans<<endl;
}
}
各クオリごとにft_sumしているためO(QlogN)、rを[1,N]区間で伸ばす際にft_addするためO(NlogN)なので、合計でO((Q+N)logN)です。
※Qmax+Nmax=10^6,logNmax≒5.7、ft_sunやft_addは二回していることを考えると、10^7の計算量で落ち着きそうです。
なのですが、1.7sほど実行時間がかかっているため、書き方がかなり悪い...。(ソートとかを加味しても、10^7なら500msくらいで落ち着いてほしい)
・8/3 20:00追記 遅いわけ
https://xuzijian629.hatenablog.com/entry/2019/03/31/130708
どうもendlはは遅いようで、
cout<<qu[i].ans<<endl;
->cout<<qu[i].ans<<"\n";
とするだけで、700ms縮まって1000msになりました。
cin.tie(nullptr); を追加、#define int long longを削除(これは意味ないかも)
で50ms縮まって950msになりました。
cinとcoutをscanfとprintfに書き換えると、500msほど縮まって480msになりました。(早い！！)
これで想定通りの早さになりました。I/Oの多い問題でcin,coutは避けた方がよさそうです。
・最後に
https://kenkoooo.com/atcoder/#/table/
atcoder problemで見た感じ、このF問題は水色上位らしいです...。
なかなか青色への道は遠そうですね。
この記事が気に入ったらサポートをしてみませんか？