2013-05-09

■ JOI typhoon 16:20

O(N log N+Q log^2 N)という普通の解答より遅い方法で解きました。

CF301Dでは左端で範囲をしぼって、右端をノードで持って二分探索で解を求める、

というふうにしました。

今回は台風のidxで範囲をしぼって、地点pが何回襲撃されたか求めたいのですが、

これは(襲撃された範囲の右端のうちp以上であるものの総数)-(襲撃された範囲の左端のうちpより大であるものの総数)で求めることができるので、

二分探索を用いることが出来ます。

以上より、解法がとても似ているので、CF301Dのコードを少し書き換えればよいです。

//typhoon
#include 
#include 
#include 
using namespace std;
#define pb push_back
vector<int>seg[(1<<18)][2];
int lim;
inline void fupdate(int num1,int num2,int poz)
{
    poz+=(1<<17)-1;
    seg[poz][0].pb(num1);
    seg[poz][1].pb(num2);
}
inline void supdate()
{
	for(int i=(1<<17)-2;i>=0;i--)
	{
		 for(int j=0;j<2;j++)
	         {
            		seg[i][j].resize(seg[i*2+1][j].size()+seg[i*2+2][j].size());
            		merge(seg[i*2+1][j].begin(),seg[i*2+1][j].end(),seg[i*2+2][j].begin(),seg[i*2+2][j].end(),seg[i][j].begin());
       		 }
	}
}
 
inline int calc(int a,int b,int k,int l,int r)
{
	if(rreturn 0;
	if(a<=l && r<=b)
	{
		int ret1=lower_bound(seg[k][1].begin(),seg[k][1].end(),lim)-seg[k][1].begin();
        	ret1=r-l+1-ret1;
        	int ret2=upper_bound(seg[k][0].begin(),seg[k][0].end(),lim)-seg[k][0].begin();
        	ret2=r-l+1-ret2;
		return ret1-ret2;
	}
	return calc(a,b,k*2+1,l,l+(r-l+1)/2-1)+calc(a,b,k*2+2,l+(r-l+1)/2,r);
}
 
 
int main()
{
    int n,q,k;
    scanf("%d %d %d",&n,&q,&k);
    for(int i=0;iint le,ri;
        scanf("%d %d",&le,&ri);
        le--; ri--;
        fupdate(le,ri,i);
    }
    supdate();
    for(int i=0;iint p,q,r;
        scanf("%d %d %d",&p,&q,&r);
        lim=p-1;
        q--; r--;
        printf("%d%c",calc(q,r,0,0,(1<<17)-1),10);
    }
}

当面はJOIの難易度9以下を埋めていきたい。

ツイートする