?
题目就是一张墙上贴海报，先贴的会被后贴的覆盖，问最后可以看到多少张海报
题目给的数据 1 <= i <= n, 1 <= li <= ri <= 10000000，
这样直接来超时先不说肯定内存都受不了的，离散化处理，映射的时候没写好，弄了挺久的，太搓了
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #define ll long long #define LL __int64 #define eps 1e-8 #define inf 0xfffffff //const LL INF = 1LL<<61; using namespace std; //vector > G; //typedef pair P; //vector > ::iterator iter; // //map mp; //map ::iterator p; const int N = 20000 + 5; typedef struct Node { int l,r; int a; }; Node tree[N * 4]; int le[N * 2],ri[N * 2]; int vis[N * 2]; int ans; typedef struct Line { int x;//区间端点 int num;//编号 }; Line line[N * 2];//离散化 void init() { memset(vis,0,sizeof(vis)); ans = 0; } bool cmp(Line x,Line y) { return x.x < y.x; } void build(int l,int r,int id) { tree[id].l = l; tree[id].r = r; tree[id].a = 0; if(l == r)return ; int mid = (l + r)/2; build(l,mid,id<<1); build(mid+1,r,id<<1|1); } void push_down(int id) { if(tree[id].a > 0) { tree[id<<1].a = tree[id].a; tree[id<<1|1].a = tree[id].a; tree[id].a = 0; } } void update(int l,int r,int id,int w) { if(l <= tree[id].l && r >= tree[id].r) { tree[id].a = w;return; } push_down(id); int mid = (tree[id].l + tree[id].r)/2; if(r <= mid)update(l,r,id<<1,w); else if(l > mid)update(l,r,id<<1|1,w); else { update(l,mid,id<<1,w); update(mid+1,r,id<<1|1,w); } } void query(int id) { if(tree[id].a > 0) { if(vis[tree[id].a] == 0) { ans++; vis[tree[id].a] = 1; } return; } query(id<<1); query(id<<1|1); } int main() { int t; scanf(%d,&t); while(t--) { init(); int n; scanf(%d,&n); for(int i=0;i ?