-1

对子数组进行按位与运算时，如何优化计算连续子数组的完全平方数的解决方案。时间复杂度应该是 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;
        }
    }
}

4

2 回答 2

2

您可以制作数字位的 Trie 数据结构并继续插入 pre_and。此外，请记住让 Node 结构存储数字的索引，以便您可以针对给定范围运行查询。现在剩下的就是计算 AND 结果是否是一个完美的正方形。自己试试吧。提示就足够了。你可以参考这个

于 2018-09-13T18:25:44.570 回答
0

ND 个数字的变化不会超过 LogN 时间，因此最多可能有 O(NLogN) 个不同的值。因此，可以在组或范围内更新答案，这可以通过段树或 fenwick 树来完成。

#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) (setter's solution) 空间复杂度=O(NLogAi) 其中Ai大约是A中的最大元素。

于 2018-09-24T13:39:56.930 回答