BZOJ 4939 [Ynoi2016]掉进兔子洞

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=4939

题意:略。

思路:继续Claris的课件题ORZ。。。不过这题要手写bitset然后就有点GG,以后再来看内部的实现方法好了。跟上一题差不多,但这里数字会出现多次,但是可以用离散化后的空位来存放这些相同的数字,然后求一下区间交最后把相同的数字减掉就好了,具体看这里

#pragma comment(linker, "/STACK:102400000,102400000")
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cmath>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <sstream>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define MOD 1000000007
#define lson root<<1,l,mid
#define rson root<<1|1,mid+1,r
#define Key_Value ch[ch[root][1]][0]
#define DBN1(a)           cerr<<#a<<"="<<(a)<<"\n"
#define DBN2(a,b)         cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<"\n"
#define DBN3(a,b,c)       cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<"\n"
#define DBN4(a,b,c,d)     cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<"\n"
#define DBN5(a,b,c,d,e)   cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<"\n"
#define DBN6(a,b,c,d,e,f) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<", "<<#f<<"="<<(f)<<"\n"
#define clr(a,x) memset(a,x,sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn=100010;
const int INF=0x3f3f3f3f;
const double PI=acos(-1.0);
template<typename T> inline T gcd(T&a,T&b){return b==0?a:gcd(b,a%b);}
template<typename T> inline T lcm(T&a,T&b){return a/gcd(a,b)*b;}
template<typename T>
inline T read(T&x){
    x=0;int _f=0;char ch=getchar();
    while(ch<'0'||ch>'9')_f|=(ch=='-'),ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x=_f?-x:x;
}
int sz,n,m,pos[maxn],block[maxn],a[maxn],cnt[maxn],ans[maxn],mark[maxn];
struct Query{
    int l,r,id;
    bool operator<(const Query&b)const{
        if (block[l]==block[b.l]) return r<b.r;
        return block[l]<block[b.l];
    }
}query[maxn<<2];
int disc[maxn];
const int maxm=1567,K=25000;
ull v[maxm],f[K+3][maxm];
int u[65537],tmp,U;
void flip(int x){v[x>>6]^=1ULL<<(x&63);}
void Copy(ull *a){
    int i=0;
    for (;i+13<=U;i+=14){
        for (int j=0;j<14;j++){
            a[i+j]=v[i+j];
        }
    }
    for (;i<=U;i++) a[i]=v[i];
}
void And(ull *a){
    int i=0;
    for (;i+13<=U;i+=14){
        for (int j=0;j<14;j++){
            a[i+j]&=v[i+j];
        }
    }
    for (;i<=U;i++) a[i]&=v[i];
}
void popcount(ull x){tmp+=u[x&65535]+u[x>>16&65535]+u[x>>32&65535]+u[x>>48];}
int Count(ull *a){
    int i=tmp=0;
    for (;i+13<=U;i+=14){
        for (int j=0;j<14;j++) popcount(a[i+j]);
    }
    for (;i<=U;i++) popcount(a[i]);
    return tmp;
}
void init(){for(int i=1;i<65536;i++)u[i]=u[i>>1]+(i&1);}
int main(){
    read(n),read(m);
    U=n>>6;
    init();
    sz=(int)sqrt(n+0.5);
    for (int i=1;i<=n;i++) read(a[i]),disc[i]=a[i],block[i]=(i-1)/sz+1;
    sort(disc+1,disc+1+n);
    for (int i=1;i<=n;i++) a[i]=lower_bound(disc+1,disc+1+n,a[i])-disc;
    int pos=0,l=1,r=0;
    while (pos<m){
        int tot=0;
        for (int i=1;i<=25000&&i+pos<=m;i++){
            tot+=3;
            ans[i]=0;
            mark[i]=0;
            read(query[i*3-2].l),read(query[i*3-2].r),query[i*3-2].id=i;
            read(query[i*3-1].l),read(query[i*3-1].r),query[i*3-1].id=i;
            read(query[i*3].l),read(query[i*3].r),query[i*3].id=i;
            ans[i]+=query[i*3-2].r-query[i*3-2].l+1;
            ans[i]+=query[i*3-1].r-query[i*3-1].l+1;
            ans[i]+=query[i*3].r-query[i*3].l+1;
        }
        sort(query+1,query+1+tot);
        for (int i=1;i<=tot;i++){
            while (r<query[i].r){flip(a[r+1]+cnt[a[r+1]]);cnt[a[r+1]]++;r++;}
            while (l>query[i].l){flip(a[l-1]+cnt[a[l-1]]);cnt[a[l-1]]++;l--;}
            while (l<query[i].l){cnt[a[l]]--;flip(a[l]+cnt[a[l]]);l++;}
            while (r>query[i].r){cnt[a[r]]--;flip(a[r]+cnt[a[r]]);r--;}
            if (mark[query[i].id]) And(f[query[i].id]);
            else Copy(f[query[i].id]),mark[query[i].id]=1;
        }
        tot/=3;
        for (int i=1;i<=tot;i++) printf("%d\n",ans[i]-3*Count(f[i]));
        pos+=tot;
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注