hdu 4737 A Bit Fun 2013成都試合区ネット試合最後の問題
タイトルはN(N<=10000000)の個数と1つのmを与え、f(i,j)がi番目からj番目の数であるか、f(i,j)方法はいろいろありますが、私が使っているのは、セグメントツリーが2つのマークで配列上を移動し、1つの区間を表す左端点1つの区間を表す右端点で、それからセグメントツリーでlognの複雑さで区間の和を求め、統計を行います.
具体的なコードは以下の通りです.
具体的なコードは以下の通りです.
/************************
hdu 4737 A Bit Fun
*************************/
#include<cstdio>
#include<cstring>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int maxn=100005;
int sum[maxn<<2],m,n,data[maxn];
int cas=0;
int build(int l,int r,int rt)//
{
if (l==r) return sum[rt]=data[l];
int m=(l + r)>>1;
return sum[rt]=build(lson)|build(rson);
}
int query(int L,int R,int l,int r,int rt) //L R ，l r rt
{
if (L<=l&&r<=R) return sum[rt];
int m=(l+r)>>1,ret=0;
if(L<=m) ret|=query(L,R,lson);
if(R>m) ret|=query(L,R,rson);
return ret;
}
int read()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&data[i]);
build(1,n,1);
return 0;
}
void deal()
{
int sta=1,en=1,ans=0,te,temp,f=0;
while(sta<=n&&en<=n)// ，
{
temp=query(sta,en,1,n,1);
if(en<n)
{
te=query(sta,en+1,1,n,1);
if(temp<m&&te>=m)
f=ans+=en-sta+1;
else if(temp>=m) f=1;
if(te<m) f=0;
}
if(temp<m&&en==n)
f=ans+=en-sta+1;
if(en==n&&temp>=m)f=1;
if(sta==en&&en<n) f=0;
f?sta++:en++;
}
printf("Case #%d: %d
",++cas,ans);
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int T;scanf("%d",&T);
while(T--)
{
read();
deal();
}
return 0;
}