Идеальный квадрат с БИТ МУДРОМ И
Как оптимизировать решение подсчета числа идеальных квадратов смежных подмассивов, когда побитовая операция И выполняется над под массивами.
Сложность времени должна быть O (n) или O (n * logn).
Вот такой наивный подход
int a[]={1,2,3,4,5,6};
int l=2,r=5;
int c=0; // for counting the subsets
for(int i=l;i<=r;i++){
int val=a[i];
for(int j=i;j<=r;j++){
val=val&a[j];
if(isPerfectSquare(val)){
c+=1;
}
}
}Решение
Вы можете создать структуру данных Trie из битов числа и продолжать вставлять pre_and. Кроме того, не забудьте сделать так, чтобы структура Node сохраняла индекс числа, чтобы вы могли выполнить запрос для заданного диапазона. Теперь осталось только вычислить, является ли результат AND идеальным квадратом. Попробуйте сами. Намек достаточно. Вы можете сослаться этот
Другие решения
ND чисел может изменяться не более чем за время LogN, и, следовательно, возможны не более O (NLogN) различных значений. Следовательно, можно обновить ответ по группе или диапазону, что можно сделать с помощью дерева сегментов или дерева фенвиков.
#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n, m, t, l, r, a[100005];
ll d[2][100005], ans[500005];
vector< pair<int, int> > rs[100005];
//vector for groups with equal AND
vector< pair<int, int> > groups;
//fenwick tree
ll sum(ll num, ll pos)
{
ll sm = 0;
while(pos >= 0)
{
sm += d[num][pos];
pos = (pos & (pos + 1)) - 1;
}
return sm;
}
void update(ll num, ll pos, ll x)
{
while(pos < n)
{
d[num][pos] += x;
pos = (pos | (pos + 1));
}
}
int main()
{
scanf("%d", &t);
while(t--)
{
scanf("%d", &n);
scanf("%d", &m);
for(int i = 0; i < n; i++)
{
scanf("%d", &a[i]);
d[0][i] = d[1][i] = 0;
rs[i].clear();
}
d[0][n] = d[1][n] = 0;
for(int i = 0; i < m; i++)
{
scanf("%d%d", &l, &r);
l--;
r--;
rs[r].push_back({l, i});
}
groups.clear();
for(int i = 0; i < n; i++)
{
//new vector for groups
vector< pair<int, int> > newgroups;
for(int j = 0; j < groups.size(); j++)
{
int cur = groups[j].first & a[i];
if(!j || cur != newgroups[newgroups.size() - 1].first)
{
newgroups.push_back({cur, groups[j].second});
}
}
if(newgroups.size() == 0 || newgroups[newgroups.size() - 1].first != a[i])
newgroups.push_back({a[i], i});
//making new vector current
groups = newgroups;
for(int j = 0; j < groups.size(); j++)
{
//checking for a perfect square
int sq = floor(sqrt(groups[j].first));
if((sq - 1) * (sq - 1) == groups[j].first || sq * sq == groups[j].first || (sq + 1) * (sq + 1) == groups[j].first)
{
//getting a borders
l = groups[j].second;
if(j != groups.size() - 1)
r = groups[j + 1].second - 1;
else
r = i;
//adding an arithmetic progression
update(0, l, (r + 1));
update(0, r + 1, -(r + 1));
update(1, l, 1);
update(1, r + 1, -1);
//adding on a prefix
update(0, 0, r - l + 1);
update(0, l, -(r - l + 1));
}
}
for(int j = 0; j < rs[i].size(); j++)
{
//getting an answer for a query
ans[rs[i][j].second] = sum(0, rs[i][j].first);
ans[rs[i][j].second] -= sum(1, rs[i][j].first) * rs[i][j].first;
}
}
for(int i = 0; i < m; i++)
{
printf("%lld\n", ans[i]);
}
}
return 0;
}Сложность времени = O (QLogN + N ∗ LogA ∗ LogN) (решение сеттера)
Сложность пространства = O (NLogAi), где Ai — максимальный элемент в A приблизительно.