题目地址 题意：两两可见的定义是对于第i条线段和第k条线段如果用一条平行线能够经过它们并且在它们之间不经过其他线段,则称这两条线段互为可见，求n条线段有多少个三条线段两两可见 思路：对x坐标进行排序，然后加线之前查询他能看到x坐标比他小的线段有哪些记录下来，然后更新，最后暴力求一遍就好了
#include <iostream> #include <cstring> #include <string> #include <queue> #include <vector> #include <map> #include <set> #include <stack> #include <cmath> #include <cstdio> #include <algorithm> #define N 8005 #define LL __int64 #define lson l,mid,ans<<1 #define rson mid+1,r,ans<<1|1 #define getMid (l+r)>>1 #define movel ans<<1 #define mover ans<<1|1 using namespace std; const LL mod = 1e9 + 7; const double eps = 1e-9; const int inf = 1 << 28; struct node { int x, y, h, id; bool operator <(const node &a)const { return h<a.h; } }num[N]; LL sum[N<<3]; bool mark[N][N]; struct Segment__Tree { int x, y; void pushDown(int ans) { if (sum[ans]) { sum[movel] = sum[mover] = sum[ans]; sum[ans] = 0; } } void build() { memset(sum, 0, sizeof(sum)); memset(mark, false, sizeof(mark)); } void solve(int l, int r, int ans, int id) { if (sum[ans]) { mark[id][sum[ans]] = true; return; } if (l == r) { return; } pushDown(ans); int mid = getMid; if (mid<x) { solve(rson, id); } else if (mid >= y) { solve(lson, id); } else { solve(lson, id); solve(rson, id); } return; } void updata(int l, int r, int ans, int nums) { if (l >= x&&r <= y) { sum[ans] = nums; return; } pushDown(ans); int mid = getMid; if (mid<x) { updata(rson, nums); } else if (mid >= y) { updata(lson, nums); } else { updata(lson, nums); updata(rson, nums); } } }; int main() { cin.sync_with_stdio(false); int T; int n; Segment__Tree tree; cin >> T; while (T--) { cin >> n; tree.build(); for (int i = 0; i < n; i++) { cin >> num[i].x >> num[i].y >> num[i].h; num[i].id = i + 1; } sort(num, num + n); for (int i = 0; i < n; i++) { tree.x = num[i].x * 2; tree.y = num[i].y * 2; tree.solve(0, N * 2, 1, num[i].id); tree.updata(0, N * 2, 1, num[i].id); } LL ans = 0; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (mark[i][j]) { for (int k = 1; k <= n; k++) { if (mark[i][k] && mark[j][k]) { ans++; } } } } } cout << ans << endl; } return 0; }