題意：有10萬個點，10萬個詢問，沒有更新，求L1<=L<=L2，R1<=R<=R2，有多少個，

? ? ? ? 其實轉換一下：就是求一個矩形 (L1,R1) ----(L2,R2) 中有多少個點（很經典的題）

? ? ? ? 這里有比較神奇的做法：基于某種性質。

? ? ? ? 解析：

? ? ? ? ? ? ? ? 首先按照 L坐標排序，每個點 也弄成 （R,R,L,0，I)這種形式

? ? ? ? ? ? ? ? 矩形形式是： （L2，R2，L,-1，I) ;和

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （L2，R2，R+1，1，I);

?　　 ? ? ? ? 那么，先按照L 排序；

struct Segment{
int x1,x2;
int y,t,id;
Segment(int x1 = 0,int x2 = 0,int y = 0,int t = 0,int id = 0):x1(x1),x2(x2),y(y),t(t),id(id){}
bool operator < (const Segment &a)const{
if(y != a.y) return y < a.y;
return abs(t) > abs(a.t);
}

?

這樣；

1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N = 100005; 4 5 #define lson l,mid,rt<<1 6 #define rson mid+1,r,rt<<1|1 7 #define Mid int mid = (l + r) >> 1 8 #define root 1,(N - 5),1 9 10 struct Segment{ 11 int x1,x2; 12 int y,t,id; 13 Segment(int x1 = 0,int x2 = 0,int y = 0,int t = 0,int id = 0):x1(x1),x2(x2),y(y),t(t),id(id){} 14 bool operator < (const Segment &a)const{ 15 if(y != a.y) return y < a.y; 16 return abs(t) > abs(a.t); 17 } 18 }ss[N * 3]; 19 int sz; 20 struct SegmentTree{ 21 int sum[N << 2]; 22 void pushup(int rt){ 23 sum[rt] = sum[rt << 1] + sum[rt << 1 | 1]; 24 } 25 void build(int l,int r,int rt){ 26 sum[rt] = 0; 27 if(l == r) return; 28 Mid; 29 build(lson); 30 build(rson); 31 } 32 void update(int loc,int l,int r,int rt){ 33 if(l == r){ 34 sum[rt] ++; 35 return; 36 } 37 Mid; 38 if(loc <= mid) update(loc,lson); 39 else update(loc,rson); 40 pushup(rt); 41 } 42 int query(int L,int R,int l,int r,int rt){ 43 if(L <= l && r <= R){ 44 return sum[rt]; 45 } 46 Mid; 47 int res = 0; 48 if(L <= mid) res += query(L,R,lson); 49 if(mid + 1 <= R) res += query(L,R,rson); 50 return res; 51 } 52 }sgt; 53 int res[N]; 54 int main() 55 { 56 int n,m,l,r; 57 int l2,r2; 58 while(~scanf("%d",&n)){ 59 sz = 0; 60 for(int i = 0 ; i < n ; i ++){ 61 scanf("%d%d",&l,&r); 62 ss[sz ++] = Segment(r,r,l,0); 63 } 64 scanf("%d",&m); 65 for(int i = 0 ; i < m ; i ++){ 66 scanf("%d%d%d%d",&l,&r,&l2,&r2); 67 ss[sz ++] = Segment(l2,r2,l,-1,i); 68 ss[sz ++] = Segment(l2,r2,r + 1,1,i); 69 } 70 71 for(int i = 0 ; i < m ; i ++) res[i] = 0; 72 sgt.build(root); 73 sort(ss,ss + sz); 74 for(int i = 0 ; i < sz ; i ++){ 75 if(ss[i].t == 0) sgt.update(ss[i].x1,root); 76 else if(ss[i].t == -1){ 77 res[ ss[i].id ] -= sgt.query(ss[i].x1,ss[i].x2,root); 78 } 79 else{ 80 res[ ss[i].id ] += sgt.query(ss[i].x1,ss[i].x2,root); 81 } 82 } 83 84 for(int i = 0 ; i < m ; i ++) printf("%d\n",res[i]); 85 } 86 return 0; 87 } View Code

先直接貼別人代碼。

?因為 我們是按照L 排序的，那么首先更新的事L在前的點。而它只可能對后面的點有影響，并且

是矩形 后面坐標 R1<=R<=R2;的點，因為詢問時詢問(R1，R2)區間，

只有一種是不符合的，R1<=R<=R2,但是L<L1的點 是不滿足的 （想想）

于是我們 只有在去除這些更新的點就好了，所以對于會有：

else if(ss[i].t == -1){
res[ ss[i].id ] -= sgt.query(ss[i].x1,ss[i].x2,root);
}

在l1<=l<=l2的點都更新完了，我們在加上R+1所有的點，就是該矩形內有多少點的答案了，比較難想。

?這道題也因為 區間比較大，所以普通 的二維樹狀數組 也是不行的

?

轉載于:https://www.cnblogs.com/forgot93/p/4641584.html

總結

以上是生活随笔為你收集整理的TOJ 4105的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。