题意是指第i此插入操作,插入一条长度为i的线段,左端点在b[i],删除某一条线段,问每次插入操作时,被当前线段完全覆盖的线段的条数。

题解:对于新插入的线段,查询有多少个线段左端点大于等于该线段的左端点。 再查询有多少个线段的右端点大于该线段右端点, 两者之差就是答案。用两个树状数组搞定。时间复杂度nlogn

由于坐标范围很大,需要离散。

#pragma comment(linker, "/STACK:1677721600")
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cmath>
#include <ctime>
#include <bitset>
#include <vector>
#include <cstdio>
#include <cctype>
#include <cstdarg>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
#define INF 0x3f3f3f3f
#define inf (-((LL)1<<40))
#define root 1, 1, n
#define lc (k << 1)
#define rc (k << 1 | 1)
#define middle ((L + R) >> 1)
#define lson k<<1, L, (L + R)>>1
#define rson k<<1|1, ((L + R)>>1) + 1, R
#define mem0(a) memset(a,0,sizeof(a))
#define mem1(a) memset(a,-1,sizeof(a))
#define mem(a, b) memset(a, b, sizeof(a))
#define FIN freopen("in.txt", "r", stdin)
#define FOUT freopen("out.txt", "w", stdout)
#define rep(i, a, b) for(int i = a; i <= b; i ++)
#define dec(i, a, b) for(int i = a; i >= b; i --) //typedef __int64 LL;
//typedef long long LL;
typedef pair<int, int> Pair;
const int MAXN = + ;
const int MAXM = ;
const double eps = 1e-10;
//LL MOD = 1000000007; struct Operator {
int type, lb;//所有操作,lb表示左边界
}op[MAXN];
int c1[MAXN], c2[MAXN], n;//两个树状数组
int h1[MAXN], h2[MAXN], L[MAXN];//用于hash,L[i]表示第i次询问的左边界 int lowbit(int x) { return x & (-x); } void update(int *c, int n, int k, int v) {
while(k <= n) {
c[k] += v;
k += lowbit(k);
}
} int query(int *c, int k) {
int ans = ;
while(k > ) {
ans += c[k];
k -= lowbit(k);
}
return ans;
} int main()
{
#ifndef ONLINE_JUDGE
FIN;
// FOUT;
#endif
int cas = ;
while(~scanf("%d", &n)) {
mem0(c1); mem0(c2);
int cnt = , sz1 = , sz2 = ;
rep (i, , n) {
scanf("%d %d", &op[i].type, &op[i].lb);
if(op[i].type == ) {
cnt ++;
h1[sz1++] = op[i].lb;
h2[sz2++] = op[i].lb + cnt;
L[cnt] = op[i].lb;
}
} sort(h1, h1 + sz1); sz1 = unique(h1, h1 + sz1) - h1;
sort(h2, h2 + sz2); sz2 = unique(h2, h2 + sz2) - h2;
printf("Case #%d:\n", ++cas); cnt = ;
rep (i, , n) {
if( !op[i].type ) { //(cnt_seg - query(c1, lb - 1)) - (cnt_seg - query(c2, rb)) = q2(rb) - q1(lb - 1)
++cnt;
int lb = lower_bound(h1, h1 + sz1, op[i].lb) - h1 + ;
int rb = lower_bound(h2, h2 + sz2, op[i].lb + cnt) - h2 + ;
printf("%d\n", query(c2, rb) - query(c1, lb - ));
update(c1, sz1, lb, );
update(c2, sz2, rb, );
}
else {
update(c1, sz1, lower_bound(h1, h1 + sz1, L[op[i].lb]) - h1 + , -);
update(c2, sz2, lower_bound(h2, h2 + sz2, L[op[i].lb] + op[i].lb) - h2 + , -);
}
}
}
return ;
}

最新文章

  1. Ubuntu管理开机启动服务项 -- 图形界面的Boot-up Manager
  2. style设置/获取样式的问题 和 offsetWidth/offsetHeight的问题
  3. WAP端 touch事件触发顺序记录
  4. SOLID原则
  5. Git 怎样保证fork出来的project和原project(上游项目)同步更新
  6. linux下的shell命令的编写,以及java怎样调用linux的shell命令(java怎样获取linux上的网卡的ip信息)
  7. xml--通过SAX解析XML
  8. iOS相关,过年回来电脑上的证书都失效了,解决方法。
  9. JavaScript encodeURI() 函数
  10. 每天一条Linux命令(OS X系统上操作)
  11. Javascript知识四(DOM)
  12. C# 如何获取某用户的“我的文档”的目录
  13. Django+xadmin打造在线教育平台(六)
  14. MySQL5.7.23解压版安装教程
  15. js中onload和jQuery中的ready区别
  16. Elasticsearch安装图形化界面工具Head插件
  17. 我的Mac Pro coding环境配置
  18. 洛谷P1101 单词方针
  19. log4net.dll添加报错
  20. Collection接口框架

热门文章

  1. LeetCode--155--最小栈
  2. 『Scrapy』爬虫框架入门
  3. vijos 1423 最短路or环(有向图)
  4. UVA-10163 Storage Keepers (0-1背包)
  5. BZOJ3544 [ONTAK2010]Creative Accounting
  6. URAL 1941
  7. apache-service的使用
  8. 快速切题 sgu117. Counting 分解质因数
  9. MySQL 中Index Condition Pushdown (ICP 索引条件下推)和Multi-Range Read(MRR 索引多范围查找)查询优化
  10. 玩转X-CTR100 l STM32F4 l U-Blox NEO-6M GPS卫星定位-nmealib解码库移植解码