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