「NOIp模拟赛10-27」c - 树状数组

定义一个非负整数序列是好的，当且仅当将序列中所有元素依次按位与之后的结果为完全平方数。

给定一个非负整数序列 $a_1,a_2,...,a_n$ ，$q$ 次询问，每次询问给出 $L,R$ ，对于子序列 $a_L,...,a_{R}$ ，求有多少个非空连续子序列是好的。

$n \leq 5*10^5, q \leq 10^6$

Solution

首先，不难发现对一个元素进行按位与操作，元素在此之后的大小是不增的，即在按位与之后的值最多只会有$log_2n$个

预处理$next[i][j]$ 表示序列上的第 $i$ 位往后最近的表示为二进制之后的第 $j$ 位为 $0$ 地方。

对于一个左端点,合法的右端点只会存在于不超过$log_2n$个区间内

通过$next$数组很容易求出这些区间

求出这些区间后,离线询问,扫描线+树状数组维护即可

Code

#include <bits/stdc++.h>

#define read() Read<int>()
#define x first
#define y second
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

inline void proc_status()
{
	ifstream t ("/proc/self/status");
	cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) <<endl;
}

template <typename T> inline int Chkmin (T &a, T b) {return a > b ? a = b, 1 : 0; }
template <typename T> inline int Chkmax (T &a, T b) {return a < b ? a = b, 1 : 0; }

namespace pb_ds{   
    namespace io{
        const int MaxBuff=1<<15;
        const int Output=1<<23;
        char B[MaxBuff],*S=B,*T=B;
		#define getc() ((S==T)&&(T=(S=B)+fread(B,1,MaxBuff,stdin),S==T)?0:*S++)
        char Out[Output],*iter=Out;
        inline void flush(){
            fwrite(Out,1,iter-Out,stdout);
            iter=Out;
        }
    }
    template<class Type> inline Type Read(){
        using namespace io;
        register char ch;
        register Type ans=0; 
        register bool neg=0;
        while(ch=getc(),(ch<'0' || ch>'9') && ch!='-');
        ch=='-'?neg=1:ans=ch-'0';
        while(ch=getc(),'0'<= ch && ch<='9') ans=ans*10+ch-'0';
        return neg?-ans:ans;
    }
    template<class Type> inline void Print(register Type x,register char ch='\n'){
        using namespace io;
        if(!x) *iter++='0';
        else{
            if(x<0) *iter++='-',x=-x;
            static int s[100]; 
            register int t=0;
            while(x) s[++t]=x%10,x/=10;
            while(t) *iter++='0'+s[t--];
        }
        *iter++=ch;
    }
}
using namespace pb_ds;

const int Maxn = 5e5 + 100, Maxm = 1e6 + 100;

int N, Q, A[Maxn], Next[35][Maxn];
vector <pii> vec[Maxn], op[Maxn], query[Maxn];

int pow2[33], vis[33];

inline void Init ()
{
	for (int i = 0; i <= 30; ++i) pow2[i] = 1 << i;
	for (int j = 0; j <= 30; ++j)
	{
		Next[j][N] = N + 1;
		for (int i = N - 1; i >= 1; --i)
		{
			if (A[i + 1] & pow2[j]) Next[j][i] = Next[j][i + 1];
			else Next[j][i] = i + 1;
		}
	}
	for (int i = 1; i <= N; ++i)
	{
		for (int j = 0; j <= 30; ++j) if (A[i] & (pow2[j])) vec[i].pb(mp(Next[j][i], j));
		sort(vec[i].begin(), vec[i].end());
		int now = i, tmp = A[i], j = 0;
		while (j < vec[i].size())
		{
			int sum = sqrt(tmp);
			int x = vec[i][j].x;
			if (sum * sum == tmp && now <= x - 1)
			{
				pii u=(pii){now, x - 1};
				if (op[i].empty() || u.x>op[i][op[i].size()-1].y+1) op[i].push_back(u);
				else op[i][op[i].size()-1].y=max(op[i][op[i].size()-1].y,u.y);
//				op[i].pb(mp(now, x - 1));
			}
			now = x;
			tmp ^= (pow2[vec[i][j].y]), ++j;
		}
		if (now <= N)
		{
			pii u=(pii){now, N};
			if (op[i].empty() || u.x>op[i][op[i].size()-1].y+1) op[i].push_back(u);
			else op[i][op[i].size()-1].y=max(op[i][op[i].size()-1].y,u.y);
//			op[i].pb(mp(now, N));
		}
	}
}

struct BIT
{
	LL sum[Maxn];
	inline void add (int x, int v) { while (x <= N) sum[x] += v, x += x & (-x); }
	inline LL query (int x) { LL ans = 0; while (x) ans += sum[x], x -= x & (-x); return ans;}
}S1, S2;

LL Ans[Maxm];

inline void Solve ()
{
	Init();
	for (int i = 1; i <= Q; ++i)
	{
		int x = read(), y = read();
		query[y].pb(mp(y, i));
		query[x - 1].pb(mp(y, -i));
	}
	for (int i = 1; i <= N; ++i)
	{
		for (int j = 0; j < op[i].size(); ++j)
		{
			S1.add (op[i][j].x, 1);
			S1.add (op[i][j].y + 1, -1);
			S2.add (op[i][j].x, op[i][j].x);
			S2.add (op[i][j].y + 1, -op[i][j].y - 1);
		}
		for (int j = 0; j < query[i].size(); ++j)
		{
			LL sum = S1.query (query[i][j].x) * (query[i][j].x + 1) - S2.query (query[i][j].x);
			if (query[i][j].y > 0) Ans[query[i][j].y] += sum;
			else Ans[-query[i][j].y] -= sum;
		}
	}
	for (int i = 1; i <= Q; ++i)
	{
		Print(Ans[i]); Ans[i] = 0;
		if (!(i % 100000)) io :: flush();
	}
	io :: flush();
}

inline void Input ()
{
	N = read(), Q = read();
	for (int i = 1; i <= N; ++i) A[i] = read(), vec[i].clear(), op[i].clear(), query[i].clear();
}

main()
{
#ifndef ONLINE_JUDGE
	freopen("c.in", "r", stdin);
	freopen("c.out", "w", stdout);
#endif
	int Testcase = read();
	while (Testcase--)
	{
		memset(S1.sum, 0, sizeof S1.sum);
		memset(S2.sum, 0, sizeof S2.sum);
		Input();
		Solve();
	}
	return 0;
}