首页 > 其他分享 >POI2011LIZ-Lollipop

POI2011LIZ-Lollipop

时间:2024-04-20 16:57:11浏览次数:24  
标签:POI2011LIZ val st second en qry Lollipop first

POI #Year2011 #构造 #妙妙题

假设能取到 \(x\),那么 \(\forall y\) , \(x,y\) 奇偶性相同,\(x>y\) ,\(y\) 一定可以是 \(x\) 的一个子区间,处理奇数和偶数的最大值,离线,从大到小做

// Author: xiaruize
const int N = 1e6 + 10;

int n, m;
int a[N], s[N];
pii st, en;
pii qry[N];
pii res[N];
struct mx
{
	int l, r, val;
} od, ev;

void solve()
{
	cin >> n >> m;
	rep(i, 1, n)
	{
		char c;
		cin >> c;
		if (c == 'T')
			a[i] = 2;
		else
			a[i] = 1;
		s[i] = a[i];
		a[i] += a[i - 1];
		if (!st.first && (a[i] & 1))
			st.first = i;
		if (a[i] & 1)
			en.first = i;
		else
			en.second = i;
	}
	rep(i, 1, m)
	{
		cin >> qry[i].first;
		qry[i].second = i;
	}
	sort(qry + 1, qry + m + 1);
	reverse(qry + 1, qry + m + 1);
	if (a[en.second] - a[st.first] > a[en.first] - a[st.second])
		od = {st.first + 1, en.second, a[en.second] - a[st.first]};
	else
		od = {st.second + 1, en.first, a[en.first] - a[st.second]};
	if (a[en.first] - a[st.first] > a[en.second] - a[st.second])
		ev = {st.first + 1, en.first, a[en.first] - a[st.first]};
	else
		ev = {st.second + 1, en.second, a[en.second] - a[st.second]};
	rep(i, 1, m)
	{
		int x = qry[i].first;
		if (x & 1)
		{
			if (x > od.val)
			{
				res[qry[i].second] = {-1, -1};
				continue;
			}
			auto [l, r, val] = od;
			while (val > x)
			{
				if (s[l] == 2)
					l++;
				else if (s[r] == 2)
					r--;
				else
					l++, r--;
				val -= 2;
			}
			res[qry[i].second] = {l, r};
			od = {l, r, val};
		}
		else
		{
			if (x > ev.val)
			{
				res[qry[i].second] = {-1, -1};
				continue;
			}
			auto [l, r, val] = ev;
			while (val > x)
			{
				if (s[l] == 2)
					l++;
				else if (s[r] == 2)
					r--;
				else
					l++, r--;
				val -= 2;
			}
			res[qry[i].second] = {l, r};
			ev = {l, r, val};
		}
	}
	rep(i, 1, m)
	{
		if (res[i].first == -1)
			cout << "NIE" << endl;
		else
			cout << res[i].first << ' ' << res[i].second << endl;
	}
}

#ifndef ONLINE_JUDGE
bool end_of_memory_use;
#endif

signed main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int testcase = 1;
	// cin >> testcase;
	while (testcase--)
		solve();
#ifndef ONLINE_JUDGE
	cerr << "Memory use:" << (&end_of_memory_use - &start_of_memory_use) / 1024.0 / 1024.0 << "MiB" << endl;
	cerr << "Time use:" << (double)clock() / CLOCKS_PER_SEC * 1000.0 << "ms" << endl;
#endif
	return 0;
}

标签:POI2011LIZ,val,st,second,en,qry,Lollipop,first
From: https://www.cnblogs.com/xiaruize/p/18147873

相关文章

  • P3514 [POI2011] LIZ-Lollipop
    很神奇的题题意:给你一个由\(0\)和\(1\)组成的序列,给出\(q\)个询问,每次询问是否有原序列是否有总和为\(x\)的子段。考虑递推,但是小答案对大答案的影响不好算。考虑大区间对小区间的影响。设当前区间为\([l,r]\),总和为sum,有\(4\)种情况\(a[l]=2,a[r]=2\);这是无......
  • Android 5.0(Lollipop)中的SurfaceTexture,TextureView, SurfaceView和GLSurfaceView
    https://blog.csdn.net/jinzhuojun/article/details/44062175SurfaceView,GLSurfaceView,SurfaceTexture以及TextureView是Android当中名字比较绕,关系又比较密切的几个类。本文基于Android5.0(Lollipop)的代码理一下它们的基本原理,联系与区别。SurfaceView从Android1.0(API......
  • Android(Lollipop/5.0) Material Design(五) 使用图片
    官网地址:https://developer.android.com/intl/zh-tw/training/material/drawables.html#DrawableTint以下图片的功能能帮助你在app中实现Material设计:·图片着色·颜色提......
  • Android(Lollipop/5.0) Material Design(三) 使用Material主题
    官网地址:https://developer.android.com/intl/zh-tw/training/material/theme.html新的Material主题提供了:系统Widgets可设置它们的调色板系统Widgets的触摸反馈动画Activit......
  • Android(Lollipop/5.0) Material Design(二) 入门指南
    官网地址:https://developer.android.com/intl/zh-tw/training/material/get-started.htmlApplytheMaterialTheme运用材料主题DesignYourLayouts 设计你的布......
  • Android(Lollipop/5.0) Material Design(一) 简介
    官网地址:https://developer.android.com/intl/zh-tw/design/material/index.html使用MaterialDesign需要api21,即Lollipop/5.0以上MaterialDesign为应用提供了:一个新的主......
  • Android(Lollipop/5.0) Material Design(六) 自定义动画
    官网地址:https://developer.android.com/intl/zh-tw/training/material/animations.html动画在Material设计中,为用户与app交互反馈他们的动作行为和提供了视觉上的连贯性。M......
  • d3.js 绘制Lollipop plot(棒棒糖图)
    棒棒糖图与普通的条形图功能相似。从图形上来看,棒棒糖图是由一条锚定在x轴或y轴上的线和点组成的。使用d3js绘制棒棒糖图很简单,因此这次为了学习d3js的一些方法,使用按......
  • P3514 [POI2011]LIZ-Lollipop
    给定长度为\(n\)的序列,里面的元素为1或2,求是否有一种方案,取出连续的一段,使得到的元素和等于给定的值,若可以则输出一种方案。多组询问,\(n,q\leq10^6\)。感觉有点水,典......