洛谷 P2787 语文1（chin1）- 理理思维

题意简述

维护字符串，支持以下操作：

0 l r k：求l~r中k的出现次数
1 l r k：将l~r中元素赋值为k
2 l r：询问l~r中最大连续1的长度

题解思路

珂朵莉树暴力赋值，排序，查询

代码

#include <set>

#include <iostream>

#define IT std::set<Node>::iterator

int n,m,opt,l,r,c[26];

char ch;

struct Node {

	int l,r,v;

	Node(const int& L,const int& R,const int& V):l(L),r(R),v(V) {}

	bool operator <(const Node& x) const { return l<x.l; };

};

std::set<Node> s;

inline int read_char() {

	std::cin>>ch; return ch>'Z'?ch-'a':ch-'A';

}

inline IT split(const int& x) {

	IT it=s.lower_bound(Node(x,0,0));

	if (it!=s.end()&&it->l==x) return it;

	--it; int L=it->l,R=it->r,V=it->v; s.erase(it);

	s.insert(Node(L,x-1,V)); return s.insert(Node(x,R,V)).first;

}

inline void assign(const int& l,const int& r,const int& v) {

	IT itr=split(r+1),itl=split(l);

	s.erase(itl,itr); s.insert(Node(l,r,v));

}

inline void sort(int l,const int& r) {

	IT itr=split(r+1),itl=split(l);

	for (register IT it=itl;it!=itr;++it) c[it->v]+=it->r-it->l+1;

	s.erase(itl,itr);

	for (register int i=0;i<26;++i)

		if (c[i]) {

			s.insert(Node(l,l+c[i]-1,i));

			l+=c[i]; c[i]=0;

		}

}

inline int query(const int& l,const int& r,const int& v) {

	IT itr=split(r+1),itl=split(l); int s=0;

	for (;itl!=itr;++itl) if (itl->v==v) s+=itl->r-itl->l+1;

	return s;

}

inline void print() {

	std::cout<<"s:\n";

	for (register IT it=s.begin();it!=s.end();++it)

		std::cout<<it->l<<' '<<it->r<<' '<<it->v<<'\n';

	std::cout<<"end\n";

}

int main() {

	std::cin>>n>>m;

	for (register int i=1;i<=n;++i) s.insert(Node(i,i,read_char()));

	for (;m;--m) {

		std::cin>>opt>>l>>r;

		if (opt==1) std::cout<<query(l,r,read_char())<<'\n';

		else if (opt==2) assign(l,r,read_char());

		else sort(l,r);

//		print();

	}

}

巴特西

洛谷 P2787 语文1（chin1）- 理理思维

题意简述

题解思路

代码

最新文章

热门文章