1

我几乎已经使用延迟传播的分段树解决了 Interviewstreet 的这个象限查询问题，但我仍然得到错误的答案，所以我需要我的代码帮助。

这是问题：

象限查询

平面上有 N 个点。第 i 个点具有坐标 (xi, yi)。执行以下查询：

  1. 反射点 i 和 j 之间的所有点，包括沿 X 轴。此查询表示为X i j
  2. 反映点 i 和 j 之间的所有点，包括沿 Y 轴。此查询表示为Y i j
  3. 计算点 i 和 j 之间有多少点，包括位于 4 个象限中的每一个。此查询表示为C i j

输入：

第一行包含 N，点数。接下来是 N 行。

第 i 行包含由空格分隔的 xi 和 yi。

下一行包含 Q 查询数。接下来的 Q 行每行包含一个查询，采用上述形式之一。

所有索引均为 1 索引。

输出：

为类型的每个查询输出一行C i j。对应的行包含 4 个整数；分别在第 1、2、3 和 4 象限中具有 [i..j] 范围内索引的点数。

约束：

1 <= N <= 100000
1 <= Q <= 100000
You may assume that no point lies on the X or the Y axis.
All (xi,yi) will fit in a 32-bit signed integer
In all queries, 1 <=i <=j <=N

样本输入：

4
1 1
-1 1
-1 -1
1 -1
5
C 1 4
X 2 4
C 3 4
Y 1 2
C 1 3

样本输出：

1 1 1 1
1 1 0 0
0 2 0 1

解释：

当查询说X i j时，这意味着获取索引 i 和 j 之间的所有点，包括并反映沿 X 轴的这些点。这里的 i 和 j 与点的坐标无关。它们是指数。i 指 i 点， j 指 j 点

C 1 4要求您“考虑索引在 {1,2,3,4} 中的点集。在这些点中，有多少分别位于第 1、第 2、第 3 和第 4 个四边形中？答案显然是 1 1 1 1。

接下来，我们沿 X 轴反映索引“2 4”之间的点。所以新的坐标是：

1 1
-1 -1
-1 1
1 1

现在C 3 4是'考虑在 {3,4} 中具有索引的点集。在这些点中，有多少分别位于第 1、第 2、第 3 和第 4 个四边形中？第 3 点在第 2 象限，第 4 点在第 1 象限。所以答案是 1 1 0 0。

当前代码

这是我在c中的解决方案：

void query(int node, int b, int e, int i, int j, char ch)
{

      if(L[node][0]!=0 || L[node][1]!=0)
    {
      if(b!=e){
      L[2*node+1][0]=L[node][0];
      L[2*node+1][1]=L[node][1];
      L[2*node+2][0]=L[node][0];
      L[2*node+2][1]=L[node][1];
      }
      if(L[node][0]%2!=0)
      {
      tmp=Q[node][0];
      Q[node][0]=Q[node][3];
      Q[node][3]=tmp;

      tmp=Q[node][1];
      Q[node][1]=Q[node][2];
      Q[node][2]=tmp;
      }
      if(L[node][1]%2!=0)
      {
      tmp=Q[node][0];
      Q[node][0]=Q[node][1];
      Q[node][1]=tmp;

      tmp=Q[node][2];
      Q[node][2]=Q[node][3];
      Q[node][3]=tmp;
      }
      L[node][0]=0;
      L[node][1]=0;

    }

      if (i > e || j < b)
          return ;


      if (b >= i && e <= j)
      {
    if(ch == 'C'){
    ans[0]+=Q[node][0];
    ans[1]+=Q[node][1];
    ans[2]+=Q[node][2];
    ans[3]+=Q[node][3];
    }
    if(ch == 'X')
    {
      if(b!=e){
      L[2*node+1][0]++;
      L[2*node+2][0]++;
      }
      tmp=Q[node][0];
      Q[node][0]=Q[node][3];
      Q[node][3]=tmp;
      tmp=Q[node][1];
      Q[node][1]=Q[node][2];
      Q[node][2]=tmp;
    }
    if(ch == 'Y')
    {
      if(b!=e){
      L[2*node+1][1]++;
      L[2*node+2][1]++;
      }
      tmp=Q[node][0];
      Q[node][0]=Q[node][1];
      Q[node][1]=tmp;
      tmp=Q[node][2];
      Q[node][2]=Q[node][3];
      Q[node][3]=tmp;
    }
    return ;
      }


       query(2 * node +1, b, (b + e) / 2, i, j,ch);
      query(2 * node + 2, (b + e) / 2 + 1, e, i, j,ch);


    Q[node][0]=Q[2*node+1][0] + Q[2*node+2][0];
    Q[node][1]=Q[2*node+1][1] + Q[2*node+2][1];
    Q[node][2]=Q[2*node+1][2] + Q[2*node+2][2];
    Q[node][3]=Q[2*node+1][3] + Q[2*node+2][3];
    return ;
}
4

1 回答 1

1

如果我正确理解您的算法，您将使用 L 数组来跟踪是否需要翻转一系列点，但将实际翻转推迟到必要时。

在这种情况下，我认为这些行可能有问题：

void query(int node, int b, int e, int i, int j, char ch)
{
  if(L[node][0]!=0 || L[node][1]!=0)
  {
    if(b!=e){
      L[2*node+1][0]=L[node][0];
      L[2*node+1][1]=L[node][1];
      L[2*node+2][0]=L[node][0];
      L[2*node+2][1]=L[node][1];
    }

假设 L[node][0] 为 1，而 L[2*node+1][0] 已经为 1。这意味着上一步想要翻转 2*node+1 处的节点，然后这一步也想要翻转这些节点。这些翻转应该取消，L[2*node+1][0] 应该变为零。

我认为您应该更改这些行以使用 xor 以便取消双翻转：

void query(int node, int b, int e, int i, int j, char ch)
{
  if(L[node][0]!=0 || L[node][1]!=0)
  {
    if(b!=e){
      L[2*node+1][0]^=L[node][0];
      L[2*node+1][1]^=L[node][1];
      L[2*node+2][0]^=L[node][0];
      L[2*node+2][1]^=L[node][1];
    }

（或者也许我误解了这种方法！）

于 2012-05-18T19:25:47.333 回答