[TS-A1487][2013中国国家集训队第二次作业]分配游戏[二分]

根据题意，设$3n$次比较中胜了$w$次，负了$l$次，平了$d$次，所有场次中胜了$W$次，负了$L$次，平了$D$次。如果一场赢了，那么$w-l$就会$+1$，相同地，$W-L$也会$+1$；如果输了一场$w-l$就会$-1$，$W-L$也会$-1$。另外，再一局中如果有一次比较平了，那么这一场就一定是平局。所以对于每次查询，二分统计分别共计胜负平的比较次数，则可知$W-L=w-l$，所以$\frac{((W+L+D)+(W-l)-D)}{2}即为答案，最后就是$D$的计算方法。$D$的大小在没有三次比较完全一样的时候等于$d$，所以只需要减去三次都一样的次数$*2$ 即可。

 #include <bits/stdc++.h>

 using namespace std;

 int n,m,N,cnt;

 int a[],b[],c[];

 pair<pair<int,int>,int>vec[];

 int getint()

 {

     int data=;

     char    ch=getchar();

     while(ch<'' || ch>'')ch=getchar();

     while(ch>='' && ch<='')data=data*+ch-,ch=getchar();

     return data;

 }

 template<class  _tp>

 _tp*    lower_bound(_tp*l,_tp*r,const _tp val)

 {

     _tp*mid;

     while(l!=r)

     {

         mid=l+((r-l)>>);

         if(*mid<val)l=mid+;

         else    r=mid;

     }

     return r;

 }

 template<class  _tp>

 _tp*    upper_bound(_tp*l,_tp*r,const _tp val)

 {

     _tp*mid;

     while(l!=r)

     {

         mid=l+((r-l)>>);

         if(*mid<=val)l=mid+;

         else    r=mid;

     }

     return r;

 }

 int main()

 {

     int i,*temp1,*temp2;

     pair<pair<int,int>,int>t;

     N=getint(),n=getint(),m=getint();

     for(i=;i<=n;++i)

     {

         a[i]=getint(),b[i]=getint(),c[i]=getint();

         vec[++cnt]=make_pair(make_pair(a[i],b[i]),c[i]);

     }

     sort(a+,a+n+);

     sort(b+,b+n+);

     sort(c+,c+n+);

     sort(vec+,vec+n+);

     for(i=;i<=m;++i)

     {

         int x,y,z,W,D,L;

         x=getint(),y=getint(),z=getint();

         W=,L=,D=;

         W+=(temp1=lower_bound(a+,a+n+,x))-a-;

         L+=(a+n+)-(temp2=upper_bound(a+,a+n+,x));

         D+=temp2-temp1;

         W+=(temp1=lower_bound(b+,b+n+,y))-b-;

         L+=(b+n+)-(temp2=upper_bound(b+,b+n+,y));

         D+=temp2-temp1;

         W+=(temp1=lower_bound(c+,c+n+,z))-c-;

         L+=(c+n+)-(temp2=upper_bound(c+,c+n+,z));

         D+=temp2-temp1;

         t=make_pair(make_pair(x,y),z);

         D-=(upper_bound(vec+,vec+n+,t)-lower_bound(vec+,vec+n+,t))<<;

         printf("%d\n",(n+(W-L)-D)>>);

     }

     return ;

 }

巴特西

[TS-A1487][2013中国国家集训队第二次作业]分配游戏[二分]

最新文章

热门文章