遅延伝搬のセグメント ツリーを使用して、Interviewstreet のこのクワドラント クエリの問題をほぼ解決しましたが、まだ間違った回答を得ているため、コードで助けが必要です。
これは質問です：
象限クエリ
平面には N 個の点があります。i 番目の点の座標は (xi, yi) です。次のクエリを実行します。
- 点 i と j の間のすべての点を、両方とも X 軸に沿って反映します。このクエリは次のように表されます。
X i j - Y 軸に沿った点も含めて、点 i と j の間のすべての点を反射します。このクエリは次のように表されます。
Y i j - 4 つの象限のそれぞれにある点 i と j の間の点の数を数えます。このクエリは次のように表されます。
C i j
入力：
最初の行には、点の数である N が含まれています。N 行が続きます。
i 番目の行には、スペースで区切られた xi と yi が含まれています。
次の行には、クエリの数 Q が含まれています。次の Q 行には、上記のいずれかの形式のクエリがそれぞれ 1 つずつ含まれています。
すべてのインデックスは 1 インデックスです。
出力：
type のクエリごとに 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 ;
}