计数排序 + 线段树优化 --- Codeforces 558E : A Simple Task
2024-08-26 08:36:59
E. A Simple Task
Problem's Link: http://codeforces.com/problemset/problem/558/E
Mean:
给定一个字符串,有q次操作,每次操作将(l,r)内的字符升序或降序排列,输出q次操作后的字符串。
analyse:
基本思想是计数排序。
所谓计数排序,是对一个元素分布较集中的数字集群进行排序的算法,时间复杂度为O(n),但使用条件很苛刻。首先对n个数扫一遍,映射出每个数字出现的次数,然后再O(n)扫一遍处理出:对于数字ai,有多少个数字在ai前面。有了这个信息,我们就可以在O(1)的时间内确定出排序后ai所在的位置。
解题思路:
对于每个Query,我们先统计出(l,r)区间内每个字母出现的次数,然后分类来排序(非升或非降)。这个更新操作就相当于:
for(int j=x; j<=y; j++)
cnt[s[j] - 'a']++;
ind = ;
for(int j=x; j<=y; j++)
{
while(cnt[ind] == )
ind++;
s[j] = ind + 'a';
cnt[ind]--;
}
但是每次这样去统计时间复杂度是O(n),对于(10^5)*(5*10^4)的时间复杂度势必超时。所以我们需要一种在区间更新和统计上时间复杂度都客观的数据结构---线段树。
我们开26棵线段树,第i棵线段树维护的是:26个字母中排第i个的字母在各个区间的数目。
这样一来,我们就可以将一个字符串S完美的融入到这26棵线段树中去,更新和查找都从上面的O(n)变为了O(logn)。其中传递更新需要用Lazy标记。
Time complexity: O(q*logn*sz)
Source code:
/*
* this code is made by crazyacking
* Verdict: Accepted
* Submission Date: 2015-07-15-21.40
* Time: 0MS
* Memory: 137KB
*/
#include <queue>
#include <cstdio>
#include <set>
#include <string>
#include <stack>
#include <cmath>
#include <climits>
#include <map>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#define LL long long
#define ULL unsigned long long
using namespace std; #define MX 100007
#define lft (idx<<1)
#define rgt (lft|1)
#define mid ((l+r)>>1)
#define rep(i,x,y) for(int i=x;i<=y;++i) int Tree[][*MX];
int Lazy[][*MX];
char s[MX]; void Build(int idx,int l,int r)
{
if(l == r)
{
int id = s[l]-'a'+;
Tree[id][idx] = ;
return;
}
Build(lft,l,mid);
Build(rgt,mid+,r);
rep(i,,) Tree[i][idx] = Tree[i][lft] + Tree[i][rgt]; //回溯pushup
} void Pushup(int id,int idx,int l,int r,int v)
{
Lazy[id][idx] = v;
Tree[id][idx] = (r-l+)*(v%);
} void Update(int id,int idx,int l,int r,int s,int e,int v)
{
if(l==s && r==e)
{
Pushup(id,idx,l,r,v);
return;
}
if(Lazy[id][idx])
{
Pushup(id,lft,l,mid,Lazy[id][idx]);
Pushup(id,rgt,mid+,r,Lazy[id][idx]);
Lazy[id][idx] = ;
}
if(e <= mid) { Update(id,lft,l,mid,s,e,v); }
else if(s > mid) { Update(id,rgt,mid+,r,s,e,v); }
else { Update(id,lft,l,mid,s,mid,v), Update(id,rgt,mid+,r,mid+,e,v); }
Tree[id][idx] = Tree[id][lft] + Tree[id][rgt];
} int Query(int id,int idx,int l,int r,int s,int e) //查询s~e这段上有多少个字母i
{
if(l == s && r == e) { return Tree[id][idx]; }
if(Lazy[id][idx])
{
Pushup(id,lft,l,mid,Lazy[id][idx]);
Pushup(id,rgt,mid+,r,Lazy[id][idx]);
Lazy[id][idx] = ;
}
if(e <= mid) { return Query(id,lft,l,mid,s,e); }
else if(s > mid) { return Query(id,rgt,mid+,r,s,e); }
else { return Query(id,lft,l,mid,s,mid) + Query(id,rgt,mid+,r,mid+,e); }
} int main()
{
int n,m;
scanf("%d %d",&n,&m);
scanf("%s",s+);
Build(,,n);
while(m--)
{
int s,e,k;
scanf("%d %d %d",&s,&e,&k);
int cnt[] = {};
rep(i,,)
{
cnt[i] = Query(i,,,n,s,e);
Update(i,,,n,s,e,);
}
if(k)/**< non-decreasing */
{
int l = s;
rep(i,,)
{
int st = l;
int ed = st+cnt[i]-;
if(st <= ed) { Update(i,,,n,st,ed,); } //将字符串的st到ed置为i
l = ed+;
}
}
else/**< non-increasing */
{
int l = s;
for(int i=; i>=; --i)
{
int st = l;
int ed = st+cnt[i]-;
if(st <= ed) { Update(i,,,n,st,ed,); }
l = ed+;
}
}
}
rep(i,,n)
{
rep(j,,)
{
int qq = Query(j,,,n,i,i);
if(qq) {putchar('a'+j-); break;}
}
}
puts("");
return ;
}
最新文章
- 使用Spring进行统一日志管理 + 统一异常管理
- 微信h5页面禁止下拉露出网页来源
- GPS围栏两个多边形相交问题的奇葩解法
- OpenCV加载图像并显示
- 在Eclipse中用图形界面的方式获取Salesforce中Object的Query语句
- Mongodb For Windows
- 【C#】1.1 第1章学习要点
- mysql备份方法
- Firefox扩展开发
- HDU-1754I Hate It 线段树区间最值
- the thread has exited with code -1073741819
- Android -- FragmentTabHost实现微信底部切换
- spring+springmvc+mybatis整合
- Linux 学习笔记 更多的bash shell命令
- Javascript 函数和模块定义
- tomcat与resin的比较
- 【DataStructure】The description of Java Collections Framework
- read cache return null
- Android ViewManager解读之requestLayout() 详解
- redis初始化服务器
热门文章
- Windows XP 中设置VPN(PPTP连接方式)
- 准备开源一套异形UI控件
- C#使用Dotfuscator混淆代码以及加密
- leetCode191/201/202/136 -Number of 1 Bits/Bitwise AND of Numbers Range/Happy Number/Single Number
- HTML5+javascript实现图片加载进度动画效果
- 精选19款华丽的HTML5动画和实用案例
- Idea 201601注册码
- Backbone之旅——Collection and View篇
- linux下备份mysql命令
- pod install 错误 - incompatible character encodings: UTF-8 and ASCII-8BIT