/*
我们把在降序部分的数设为0 ,在升序部分的数设为1 。
1. .如果降序操作把一部分升序的数变到了降序区,其实就是把为 1 的数中较小的那几个数变为0。
2. 如果升序操作把一部分降序的数变到了升序区,其实就是把为 0 的数中较小的那几个数变为1。
这么一看,其实就是修改操作,那么不就是线段树区间修改吗?
*/
/*
#pragma GCC diagnostic error "-std=c++11"
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<stack>
#include<set>
#include<ctime>
#define iss ios::sync_with_stdio(false)
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int,int> pii;
const int mod=1e9+7;
const int MAXN=2e5+5;
const int inf=0x3f3f3f3f;
std::vector<int> v[2];
struct node
{
int l,r;
int sum;
int lazy;
}node[MAXN<<1];
void push_up(int num)
{
node[num].sum=node[num<<1].sum+node[num<<1|1].sum;
}
void push_down(int num)
{
if(node[num].lazy==-1) return;
node[num<<1].lazy=node[num<<1|1].lazy=node[num].lazy;
node[num<<1].sum=(node[num<<1].r-node[num<<1].l+1)*node[num].lazy;
node[num<<1|1].sum=(node[num<<1|1].r-node[num<<1|1].l+1)*node[num].lazy;
node[num].lazy=-1;
}
void build(int l,int r,int num)
{
node[num].l=l;
node[num].r=r;
node[num].lazy=-1;
if(l==r)
{
node[num].sum=1;
return;
}
int mid=(l+r)>>1;
build(l,mid,num<<1);
build(mid+1,r,num<<1|1);
push_up(num);
}
void updata1(int val,int num)//改为1
{
int cnt=node[num].r-node[num].l+1-node[num].sum;
if(cnt<=val)
{
node[num].sum=node[num].r-node[num].l+1;
node[num].lazy=1;
return;
}
push_down(num);
int mid=(node[num].l+node[num].r)>>1;
int cnt1=node[num<<1].r-node[num<<1].l+1-node[num<<1].sum;
int cnt2=node[num<<1|1].r-node[num<<1|1].l+1-node[num<<1|1].sum;
if(cnt1>=val)
{
updata1(val,num<<1);
}
else
{
updata1(cnt1,num<<1);
updata1(val-cnt1,num<<1|1);
}
push_up(num);
}
void updata2(int val,int num) //改为0
{
int cnt=node[num].sum;
if(cnt<=val)
{
node[num].sum=0;
node[num].lazy=0;
return;
}
push_down(num);
// int mid=(node[num].l+node[num].r)>>1;
int cnt1=node[num<<1].sum;
int cnt2=node[num<<1|1].sum;
if(cnt1>=val)
{
updata2(val,num<<1);
}
else
{
updata2(cnt1,num<<1);
updata2(val-cnt1,num<<1|1);
}
push_up(num);
}
int query(int pos,int num)
{
if(node[num].l==node[num].r)
{
return node[num].sum;
}
push_down(num);
int mid=(node[num].l+node[num].r)>>1;
if(pos<=mid)
{
return query(pos,num<<1);
}
else return query(pos,num<<1|1);
}
int main()
{
int n,m;
cin>>n>>m;
build(1,n,1);
int pre=1;
while(m--)
{
int op,x;
cin>>op>>x;
if(op==1)
{
if(x>=pre) continue;
updata1(pre-x,1);
pre=x;
}
else
{
if(x<pre) continue;
updata2(x-pre+1,1);
pre=x+1;
}
}
for(int i=1;i<=n;i++)
{
int ans=query(i,1);
if(ans==0) v[0].push_back(i);
else v[1].push_back(i);
}
for(int i=v[0].size()-1;i>=0;i--)
{
cout<<v[0][i]<<" ";
}
for(auto i:v[1])
{
cout<<i<<" ";
}
}
*/
思维+栈
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
const int N = 1e5 + 10;
typedef pair<int, int> pii;
int n, m;
pii stk[N];
int ans[N];
int main() {
cin >> n >> m;
int top = 0; // 定义栈顶
while (m --) {
int p, q; cin >> p >> q;
if (!p) { // p == 0, 前缀操作
while (top && stk[top].x == 0) q = max(q, stk[top --].y); // 两个连续的前缀操作,保留较大的
while (top >= 2 && stk[top - 1].y <= q) top -= 2; // 删掉前面所有比当前长度小的操作
stk[ ++ top] = {0, q}; // 把当前的前缀操作加入栈里
}
else if (top) { // 后缀操作
while (top && stk[top].x == 1) q = min(q, stk[top --].y); // 两个连续的后缀操作,保留较小的
while (top >= 2 && stk[top - 1].y >= q) top -= 2; // 删掉前面的同类操作
stk[ ++ top] = {1, q}; // 记录当前操作
}
}
cout<<top<<endl;return 0;
int k = n, l = 1, r = n;
for (int i = 1; i <= top; i ++) { // 从前往后处理一下所有的询问
if (stk[i].x == 0) // 前缀:该区间的右端点是可以固定的
while (r > stk[i].y && l <= r) ans[r --] = k --;
else // 同理
while (l < stk[i].y && l <= r) ans[l ++] = k --;
if (l > r) break; // 表示区间为空了
}
if (top % 2) // 如果操作数是奇数, 做完了右区间,还剩一个左区间
while (l <= r) ans[l ++] = k --;
else // 如果操作数是偶数, 做完了左区间,还剩一个右区间
while (l <= r) ans[r --] = k --;
for (int i = 1; i <= n; i ++) cout << ans[i] << ' ';
return 0;
}