首页 > 其他分享 >题解:P11262 [COTS 2018] 题日 Zapatak

题解:P11262 [COTS 2018] 题日 Zapatak

时间:2024-11-11 21:09:46浏览次数:4  
标签:return Zapatak int 题解 top mid 题日 maxN check

https://www.luogu.com.cn/article/i7ajvm8e

哈希好题。


题意

给定一个序列,每次询问给定两个长度相等的区间,问这两个区间是否只有一个数不一样。

思路

发现我们要求的信息只与数的出现次数有关,自然想到桶。那么如果有两个区间合法,那这两个区间的桶只有两个位置不同且桶内的值均相差 \(1\)。

维护每个区间的桶不太能直接做,且信息明显可差分,直接套一个主席树。

在树上二分找不同的位置进行判断即可。

如果当前区间完全相等那么不满足条件,左右都不相等的情况只能出现一次不然不合法,左右只有一个不相等递归那边不相等的即可。

代码

我的实现需要注意的细节还是挺多的。

复杂度 \(O(n\log n)\)。

#include <bits/stdc++.h>

using namespace std;

using ubt = unsigned long long;

const int maxN = 1e5 + 7;

int n, m, Q;
int sor[maxN];
int a[maxN], T[maxN];

const ubt Base = 13331;
ubt B[maxN];

int top[maxN], tot;
struct dat {
  int l, r;
  int len;
  ubt H;
} t[maxN * 20];
void upd(int p) {
  t[p].H = B[t[t[p].l].len] * t[t[p].r].H + t[t[p].l].H;
}
void build(int l, int r, int &p) {
  p = ++tot;
  t[p].len = r - l + 1;
  if (l == r) return;
  int mid = (l + r) >> 1;
  build(l, mid, t[p].l);
  build(mid + 1, r, t[p].r);
  upd(p);
}
void insert(int &p, int w, int K, int l, int r) {
  p = ++tot;
  t[p] = t[w];
  if (l == r) {
    t[p].H = T[K];
    return;
  }
  int mid = (l + r) >> 1;
  if (K <= mid) insert(t[p].l, t[w].l, K, l, mid);
  else insert(t[p].r, t[w].r, K, mid + 1, r);
  upd(p);
}

ubt get(int l, int r) {
  return t[r].H - t[l].H;
}
bool Flag;
bool check(int x0, int y0, int x1, int y1, int l, int r) {
  auto t0 = get(x0, y0), t1 = get(x1, y1);
  if (t0 == t1) return false;
  if (l == r) {
    auto res = abs((int)t0 - (int)t1) == 1;
    return res;
  }
  auto L = get(t[x0].l, t[y0].l) != get(t[x1].l, t[y1].l);
  auto R = get(t[x0].r, t[y0].r) != get(t[x1].r, t[y1].r);
  int mid = (l + r) >> 1;
  if (L && R) {
    if (Flag) return false;
    Flag = true;
    return check(t[x0].r, t[y0].r, t[x1].r, t[y1].r, mid + 1, r)
      && check(t[x0].l, t[y0].l, t[x1].l, t[y1].l, l, mid);
  }
  return R ? check(t[x0].r, t[y0].r, t[x1].r, t[y1].r, mid + 1, r)
    : check(t[x0].l, t[y0].l, t[x1].l, t[y1].l, l, mid);
}

int main() {
  ios::sync_with_stdio(false), cin.tie(nullptr);

  cin >> n >> Q;
  for (int i = 1; i <= n; i++)
    cin >> a[i];

  for (int i = 1; i <= n; i++)
    sor[i] = a[i];
  sort(sor + 1, sor + n + 1);
  m = unique(sor + 1, sor + n + 1) - sor - 1;
  for (int i = 1; i <= n; i++)
    a[i] = lower_bound(sor + 1, sor + m + 1, a[i]) - sor;

  B[0] = 1;
  for (int i = 1; i <= m; i++) 
    B[i] = B[i - 1] * Base;

  build(1, m, top[0]);
  for (int i = 1; i <= n; i++) {
    T[a[i]]++;
    insert(top[i], top[i - 1], a[i], 1, m);
  }

  while (Q--) {
    int l, r, a, b;
    cin >> l >> r >> a >> b;
    Flag = false;
    bool res = check(top[l - 1], top[r], top[a - 1], top[b], 1, m);
    puts(res ? "DA" : "NE");
  }
}

标签:return,Zapatak,int,题解,top,mid,题日,maxN,check
From: https://www.cnblogs.com/ccxswl/p/18540575

相关文章

  • P8162 [JOI 2022 Final] 让我们赢得选举 (Let's Win the Election) 题解
    P8162[JOI2022Final]让我们赢得选举(Let'sWintheElection)题解朴素的想法是先抓一部分人,再一起去发表演讲。这样就要按\(b\)的值从小到大排序,枚举选择的一部分\(b\)值,在后面挑选一些最小的\(a\)选择即可。但这样显然是错误的。观察到\(n\le500\),显然是\(O(n^3......
  • 题解:P11062 【MX-X4-T2】「Jason-1」加法
    一道简单的分讨。思路可分成两种情况。当\(a\)和\(b\)同号时:这种情况,显而易见的是\(|a-b|\)的最小值必定是\(|a|,|b|,|a-b|\)之一。当\(a\)和\(b\)异号时:对\((a,b)\)执行欧几里得算法可以将一个变为\(0\),另一个变为\(\gcd(a,b)\)(忽略正负号)。再将\(0\)变......
  • 题解:P10967 [IOI2000] 邮局(原始版)
    思路首先将坐标排序。定义\(dp_{i,j}\)为前\(i\)个村庄放\(j\)个邮局的前\(i\)个村庄的最小距离总和,\(f(i,j)\)表示村庄区间\([i,j]\)内放一个村庄时该区间的总和。转化式易得\(dp_{i}{j}=dp_{k}{j-1}+f(k+1,i),k\in[0,i)\)。则本题的难点就为求\(f(k-1,i)\)。......
  • 题解:UVA1362 Exploring Pyramids
    思路:显然的,若不是叶子结点都应该至少遍历两次。于是两个相同访问之间就可能是一颗子树。更加具体的,如同\(s_l,\dots,s_k,\dots,s_r\),使得\(s_l=s_k\),那么就可以认为\(s[l,k]\)是\(s[l,r]\)的一颗子树,设区间\(s[l,r]\)的结构数量为\(f_{l,r}\),那么根据乘法原理,当把\(......
  • 241111 noip 题解
    省流:\(100+50+10+30\)。还是不稳定啊,noip上不了270就真的要退役了。T1题意:给定一个长度为\(n\)的序列\(a\),每次你可以交换相邻两个位置,求出最小交换次数以及字典序最小的交换方案使得\(a\)的每个不是本身的前缀都不是排列。\(n\leq10^5\)。注意到每次交换至多会减少一......
  • [题解]P11233 [CSP-S 2024] 染色
    P11233[CSP-S2024]染色设\(f[i][j=0/1]\)表示涂到第\(i\)位,且第\(i\)为颜色为\(j\),则考虑用\(i\)之前能和\(i\)匹配的位置\(p\)进行转移。\(p\)需要满足下面的条件:\(a[p]=a[i]\)。\(p\)的颜色为\(j\)。\([p+1,i-1]\)之间的颜色全不为\(j\)。显然,我们只需要找满足条件的......
  • AT_agc012_f [AGC012F] Prefix Median 题解
    首先将序列排序,这是显然的。考虑倒着确定\(b\)序列中的每个数。即从完整的\(a\)序列开始,每次删掉两个数,记录中位数。先找出\(b\)序列合法的条件。容易发现对于所有\(i\),在\(b_{p_i}\)成为中位数时,\(p_i,p_{i+1}\)之间的所有数都已经被删除了,且\(i\lep_i\le2n-i\)。......
  • Eplan2022卡顿问题解决
    EPLAN2022卡顿崩溃怎么解决 第一步:可以检查下用户设置。打开菜单"选项→设置:用户→翻译→字典":不勾选"自动完成"和"自动更正"。在选项设置框中输入"自动",快速找到用户设置,取消勾选,如下图。 第二步:可以检查下电脑语言设置。设置:常规→兼容性"。如下图。 ......
  • CF 1257 题解
    CF1257题解ATwoRivalStudents每次交换都可以让距离增加\(1\),上界是\(n-1\).题目说至多而不是恰好交换\(x\)次,于是不需要考虑边界.BMagicStick一个重要的观察是:如果能够得到\(x\),那么就能得到任意小于等于\(x\)的数,这是操作二保证的.考虑操作\(1\)......
  • 2024中高级前端面试真题解析
    我是一名本科毕业的前端程序媛,工作5年了,周末双休待遇还不错。公司最近要搬迁新地址,业务要整合到一起,所以最近比较清闲,天天上班摸鱼,闲着没事,整理了以前面试时用的资料文档有945道:JavaScript(323题)CSS(61题)HTML(57题)React(83题)Vue(80题)算法(19题)计算机网络(71题)Node.js(2......