首页 > 其他分享 >CF240F (26颗线段树计数)

CF240F (26颗线段树计数)

时间:2022-10-16 15:01:33浏览次数:82  
标签:tmp CF240F 26 int 线段 tr lazy mid

题目链接:Topcoder----洛谷

题目大意:

  给定一个长为n的由a到z组成的字符串,有m次操作,每次操作将[l,r]这些位置的字符进行重排,得到字典序最小的回文字符串,如果无法操作就不进行。

思路:

  用26颗线段树分别统计在每个位置上是否有对应的字母

  每次操作:

    1.有出现次数为奇数的字母:

      大于1,不可能回文,无法操作。

      等于1,放到中间

    2.全是偶数次数:

      分别放两端

  1 # include<bits/stdc++.h>
  2 using namespace std;
  3 #define endl "\n"
  4 # define int long long
  5 # define ls u<<1
  6 # define rs u<<1|1
  7 const int N = 1e5 + 10;
  8 char a[N], p;
  9 int n, m;
 10 struct segtree {
 11     int sum[4 * N], lazy[4 * N];
 12     void pushup(int u) {
 13         sum[u] = (sum[ls] + sum[rs]);
 14     }
 15 
 16     void build(int tr, int u, int l, int r) {
 17         lazy[u] = -1;
 18         if (l == r) {
 19             sum[u] = ((a[l] - 'a' ) == tr);
 20             return;
 21         }
 22         int mid = l + r >> 1;
 23         build(tr, ls, l, mid);
 24         build(tr, rs, mid + 1, r);
 25         pushup(u);
 26     }
 27 
 28     void pushdown(int u, int l, int r) {
 29         int mid = l + r >> 1;
 30         if (lazy[u] != -1) {
 31             sum[ls] = (mid - l + 1) * lazy[u];
 32             sum[rs] = (r - mid) * lazy[u];
 33 
 34             lazy[ls] = lazy[u];
 35             lazy[rs] = lazy[u];
 36             lazy[u] = -1;
 37         }
 38 
 39     }
 40 
 41     void modify(int u, int l, int r, int L, int R, int c) {
 42         if (l > r || l > R || r < L) return;
 43         if (L <= l && r <= R) {
 44             sum[u] = (r - l + 1) * c;
 45             lazy[u] = c;
 46             return;
 47         }
 48         int mid = l + r >> 1;
 49         pushdown(u, l, r);
 50         if (L <= mid) modify(ls, l, mid, L, R, c);
 51         if (mid + 1 <= R) modify(rs, mid + 1, r, L, R, c);
 52         pushup(u);
 53     }
 54 
 55     int query(int u, int l, int r, int L, int R) {
 56         if (l > r || l > R || r < L) return 0;
 57         if (l >= L && r <= R) {
 58             return sum[u];
 59         }
 60         pushdown(u, l, r);
 61         int mid = l + r >> 1;
 62         int ans = 0;
 63         if (L <= mid) ans += query(ls, l, mid, L, R);
 64         if (R > mid) ans += query(rs, mid + 1, r, L, R);
 65         return ans;
 66     }
 67 } tr[26];
 68 
 69 signed main() {
 70     ios::sync_with_stdio(false);
 71     cin.tie(0);
 72     cout.tie(0);
 73     freopen("input.txt", "r", stdin);
 74     freopen("output.txt", "w", stdout);
 75     cin >> n >> m;
 76     string s;
 77     cin >> s;
 78     for (int i = 1; i <= n; ++i) a[i] = s[i - 1];
 79     for (int i = 0; i < 26; ++i) tr[i].build(i, 1, 1, n);
 80     for (int t = 1; t <= m; ++t) {
 81         int l, r;
 82         cin >> l >> r;
 83         int odd = 0;
 84         int tmp[26] = {0}, key;
 85         for (int i = 0; i < 26; ++i) tmp[i] = tr[i].query(1, 1, n, l, r);//记录在区间[l,r]中每个字母出现的次数
 86         for (int i = 0; i < 26; ++i) if (tmp[i] & 1) odd++, key = i;
 87         if (odd > 1) continue;
 88         for (int i = 0; i < 26; ++i) tr[i].modify(1, 1, n, l, r, 0);
 89         if (odd) {
 90             --tmp[key];
 91             tr[key].modify(1, 1, n, (l + r) / 2, (l + r) / 2, 1);//奇数置中
 92         }
 93         int nl = l, nr = r;
 94         for (int i = 0; i < 26; ++i) {//偶数分两边放
 95             if (tmp[i]) {
 96                 tr[i].modify(1, 1, n, nl, nl + tmp[i] / 2 - 1, 1);
 97                 nl += tmp[i] / 2;
 98                 tr[i].modify(1, 1, n, nr - tmp[i] / 2 + 1, nr, 1);
 99                 nr -= tmp[i] / 2;
100             }
101         }
102     }
103     for (int i = 1; i <= n; ++i) {
104         for (int j = 0; j < 26; ++j) {
105             if (tr[j].query(1, 1, n, i, i)) {
106                 cout << (char)(j + 'a');
107             }
108         }
109     }
110     return 0;
111 }

 

 

标签:tmp,CF240F,26,int,线段,tr,lazy,mid
From: https://www.cnblogs.com/empty-y/p/16796213.html

相关文章

  • 2022-2023-1 20221326《计算机基础与程序设计》第七周学习总结
    班级链接:https://edu.cnblogs.com/campus/besti/2022-2023-1-CFAP作业要求:https://www.cnblogs.com/rocedu/p/9577842.html#WEEK07作业目标:数组与链表,基于数组和基于链表实......
  • 【数学篇】05 # 如何用向量和坐标系描述点和线段?
    说明【跟月影学可视化】学习笔记。坐标系与坐标映射​​HTML​​:采用的是窗口坐标系,以参考对象(参考对象通常是最接近图形元素的position非static的元素)的元素盒子左上角......
  • 线段树模板
    线段树是一种通用的数据结构,能够处理满足结合律的信息。前置知识线段树基础版structnode{intl,r;//TODO:informationandtagintlazy,val;......
  • 226. 翻转二叉树
    题目描述解题思路二叉树的题一般都有对应的模板,我们做题时可以参考对应模板二叉树解题的思维模式分两类:1、是否可以通过遍历一遍二叉树得到答案?如果可以,用一个trav......
  • 洛谷 P8268 [USACO22OPEN] Alchemy B 题解
    Part0题意简述原题给出拥有的金属数量与金属配方,求金属\(N\)最大能合成的数量。Part1题目分析首先,金属\(i\)能配出的最大数量只和它的原数量和它的配方中能合......
  • 2022-09-26-大佬们请看一下
    layout:postcid:31title:大佬们请看一下slug:31date:2022/09/2620:02:00updated:2022/10/0216:59:52status:waitingauthor:admincategories:默认分类......
  • 操作系统导论习题解答(26. Concurrency and Threads)
    Concurrency:AnIntroduction我们这里引入了thread(线程)的概念,与前面所说process(进程)的区别如下:线程之间进行上下文切换地址空间保持不变。每个线程都将有一个stack。......
  • FFmpeg H265解码总结
    背景:项目开发需要,通过TCP协议与视频板进行通信,获取图像数据,对图像数据进行解码后显示。关键词:C#、FFmpeg、FFmpeg.AutoGen.dll、WriteableBitmap、H265、HEVC1.初设计......
  • 从零开始配置vim(26)——LSP UI 美化
    之前我们通过几个实例演示如何配置其他语言的lsp服务,相信各位小伙伴碰到其他的编程语言也能熟练的配置它对应的lsp服务。本篇讲作为一个补充,我们来优化一下LSP相关的显示......
  • 26. 删除有序数组中的重复项
    题目描述给你一个升序排列的数组nums,请你原地删除重复出现的元素,使每个元素只出现一次,返回删除后数组的新长度。元素的相对顺序应该保持一致。由于在某些语......