単調性最適化-hdu-4737-A Bit Fun

タイトルリンク:
http://acm.hdu.edu.cn/showproblem.php?pid=4737
タイトル:
n個の数がある、区間L,Rの数を求める、その区間内のすべての数または値がmより小さいようにする.
問題解決の考え方:
この試合で暴力を振るったことがある.データがあまりにも水で説明しない.
この問題は単調性を利用して時間の複雑さを低減することができる.
セグメントを求め、jで終わる適切な構成または値がm未満のiを順次見つけ、その後、その区間【i,j】を含むすべての区間を除去する.
コード:

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<ctime>
#define eps 1e-6
#define INF 0x3fffffff
#define PI acos(-1.0)
#define ll __int64
#define lson l,m,(rt<<1)
#define rson m+1,r,(rt<<1)|1
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;

#define Maxn 110000
//                         ，     
int bit[35],num[35],sa[Maxn]; //bit[i]=2^i

int main()
{
    int t,n,m;

    bit[0]=1;
    for(int i=1;i<=31;i++)
        bit[i]=bit[i-1]*2;

    scanf("%d",&t);
    for(int ca=1;ca<=t;ca++)
    {
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
            scanf("%d",&sa[i]);
        int i=1,j=1,last=1;
        memset(num,0,sizeof(num));
        ll ans=(ll)n*(n+1)/2; //   +1，          ，      
        while(j<=n)
        {
            for(int k=0;k<=31;k++)
                if(sa[j]&(1<<k))
                    num[k]++;  //      1，       1
            int sum=0;
            for(int k=0;k<=31;k++)
                if(num[k])
                    sum+=bit[k];
            if(sum>=m) //  
            {
                while(sum>=m) //       
                {
                    for(int k=0;k<=31;k++)
                        if(sa[i]&(1<<k))
                            num[k]--;    //      1
                    sum=0;
                    for(int k=0;k<=31;k++)
                        if(num[k])
                            sum+=bit[k];
                    i++;
                }
                //printf(":::%d %d
",i,j);
                ans-=(ll)(i-last)*(n-j+1); //         
                last=i;//    ，    
            }
            j++;
        }
        printf("Case #%d: %I64d
",ca,ans);
    }
   return 0;
}