c++ - 范围查询所需的高效算法

Question

我想知道实现这个(方法)的最佳方法。我将蜜蜂给定一组坐标 (x,y)。然后我会根据这些坐标查询我
1.C a b => 其中a和b是初始坐标集中的整数索引。所以我需要输出索引范围 a 到 b 中的第一、第二、第三和第四象限中的点数。

2.X a b => 其中 a 和 b 是初始坐标集中的整数索引。所以我需要沿 x 轴将 ath 镜像到 bth 索引坐标。

3.Y a b => 其中 a 和 b 是初始坐标集中的整数索引。所以我需要沿 y 轴将 ath 镜像到 bth 索引坐标。

最多可以有 100000 个坐标或点以及 500000 个此类查询。

我在每个查询上尝试了一种强力循环遍历的方法，但它有 TLE(超出时间限制)。

遇到这种题该怎么办？

这是我的代码

#include <iostream>
#include <stdio.h>

using namespace std;

char flipX[4] = { 3, 2, 1, 0 };
char flipY[4] = { 1, 0, 3, 2 };

int main(int argc, char **argv)
{
    int n,x,y;
    char c[100000];
    scanf("%d",&n);
    //coord *c=new coord[n];
    for(int i=0;i<n;i++)
    {
        scanf("%d",&x);
        scanf("%d",&y);
        if(x<0 && y<0)
            c[i]=2;
        else if(x>0 && y>0)
            c[i]=0;
        else if(x>0 && y<0)
            c[i]=3;
        else
            c[i]=1;
    }

    int q,i,j,a,cnt[4];
    char ch;
    scanf("%d",&q);
    while(q--)
    {
        //cout<<"q:"<<q<<endl;
        cin>>ch;
        scanf("%d",&i);
        scanf("%d",&j);
        i--;j--;
        if(ch=='X')
        {
            //case 'X':
                for(a=i;a<=j;a++)
                    c[a]=flipX[c[a]];
            //  break;
        }
        else if(ch=='Y')
        {
            //case 'Y':
                for(a=i;a<=j;a++)
                    c[a]=flipY[c[a]];
            //  break;
        }   
        else if(ch=='C')
        {
                cnt[0]=cnt[1]=cnt[2]=cnt[3]=0;
                for(a=i;a<=j;a++)
                {
                    cnt[c[a]]++;
                }
                printf("%d %d %d %d\n",cnt[0],cnt[1],cnt[2],cnt[3]);
        }
    }
    return 0;
}

请帮助。

Answer 1

同意 nneonneo 的观点。

const size_t MAX_COORDS = 100000;
vector<char> quadrant( MAX_COORDS );

这里，quadrant 维护一个值(0 到 3)。在没有任何条件的情况下翻转象限非常简单:

char flipX[4] = { 2, 3, 0, 1 };
char flipY[4] = { 3, 2, 1, 0 };

vector<char>::iterator itLeft = quadrant.begin() + left;
vector<char>::iterator itRight = quadrant.begin() + right + 1;

for( vector<char>::iterator it = itLeft; it != itRight; it++ )
{
    *it = flipX[*it];
}

而且计算象限也同样容易:

unsigned int count[4] = {0};
for( vector<char>::iterator it = itLeft; it != itRight; it++ )
{
    count[*it]++;
}

如果您需要比这更快，则必须采用动态编程方法并记住每个点和每个象限的象限计数。这将为您提供 O(1) 范围搜索，但会使镜像操作更加昂贵。以下是范围计数的工作原理:

vector< vector<char> > counts( 4, vector<char>(MAX_COORDS) );

// ...

for( size_t i = 0; i < 4; i++ ) {
    count[i] = counts[i][right] - (left > 0 ? counts[i][left-1] : 0);
}