0

我想知道实现这一点的最佳方法（方法）。我将得到一组坐标（x，y）。然后，我将根据像
1.C ab => 这样的坐标进行查询，其中 a 和 b 是初始坐标集中的整数索引。所以我需要输出在索引范围 a 到 b 内的第一、第二、第三和第四象限的点数。


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


3.Y ab => 其中 a 和 b 是初始坐标集中的整数索引。所以我需要将 ath 镜像到沿 y 轴的 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;
}

请帮忙。

4

2 回答 2

1

同意neonneo。

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);
}
于 2012-09-27T03:18:27.543 回答
0

好的。惰性线段树做到了这一点。感谢大家的帮助

于 2012-10-04T05:55:19.550 回答