Mayor’s posters

离散化

#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;

const int maxN = 1e5 + 7;

struct Tree {
  int l, r, color, tag;
}t[maxN << 4];

int T, n, l[maxN], r[maxN], vis[maxN], ans;

vector<int> pos;

inline int getPos(int x)
{
  return lower_bound(pos.begin(), pos.end(), x) - pos.begin(); //返回第一个大于或等于x的数字
}

void build(int l, int r, int num)
{
  t[num].l = l; t[num].r = r;
  t[num].color = 0;                     //标记海报
  t[num].tag = -1;                      //延时标记
  if(l == r)
    return ;
  int mid = (l + r) >> 1;
  build(l, mid, num << 1);
  build(mid + 1, r, num << 1 | 1);
}

void spread(int num)                     //更新子节点
{
  if(t[num].tag != 0) {                  //延迟标记未更新
    t[num << 1].color = t[num].color;
    t[num << 1 | 1].color = t[num].color;
    t[num << 1].tag = t[num << 1 | 1].tag = 1;
    t[num].tag = 0;                      //父节点标记已更新到子节点
  }
}

void change(int l, int r, int num, int x)
{

  if(l <= t[num].l && r >= t[num].r) {   //覆盖节点修改标记
    t[num].color = x;
    t[num].tag = 1;                      //标记更新
    return ;
  }
  spread(num);
  int mid = (t[num].l + t[num].r) >> 1;
  if(l <= mid)
    change(l, r, num << 1, x);
  if(r > mid)
    change(l, r, num << 1 | 1, x);
}

void query(int l, int r, int num)
{
  if(t[num].tag == -1)                     //墙面空白
    return ;
  if(t[num].tag != 0) {                    //延迟标记
    if(!vis[t[num].color] && t[num].color != 0) {              //已记录的海报和白墙不记录
      ++ans;
      vis[t[num].color] = 1;
    }
    return ;
  }
  query(l, r, num << 1); query(l, r, num << 1 | 1);
}

int main()
{
  scanf("%d", &T);                           //测试用例
  while(T--) {
    scanf("%d", &n);                         //操作次数
    ans = 0;
    memset(vis, 0, sizeof vis);              //初始化
    pos.clear(); pos.push_back(0);           //清空pos中的元素，从后插入0
    for(int i = 1; i <= n; ++i) {
      scanf("%d%d", &l[i], &r[i]);           //记录海报区间节点
      pos.push_back(l[i]);
      pos.push_back(r[i]);
      pos.push_back(r[i] + 1);               //防止后续点不相邻的点在离散化后和它相邻
    }
    sort(pos.begin(), pos.end());            //排序
    pos.erase(unique(pos.begin(), pos.end()), pos.end());         //将重复的区域删除
    int len = pos.size() , cnt = 0;
    build(1, len, 1);                        //建树
    for(int i = 1; i <= n; ++i) {
      l[i] = getPos(l[i]); r[i] = getPos(r[i]);
      change(l[i], r[i], 1, ++cnt);
    }
    query(1, len, 1);
    printf("%d\n", ans);
  }
  return 0;
}

笔记：将操作区间的左右区间离散化，节省空间，但是为了避免出现海报覆盖错误的问题需要加上 r[i]+1 ,以下表格是示例输入的5次操作，输出①②④⑤四张海报

	1	2	3	4	5	6	7	8	10	…
Ⅰ	①	①	①	①
Ⅱ		②	②	②	②	②
Ⅲ								③	③
Ⅳ			④	④
Ⅴ							⑤	⑤	⑤

版权声明：

本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。本文链接：https://blog.csdn.net/SGDBS233/article/details/124465681