【LOJ #3095】【SNOI2019】—字符串（模拟）

传送门

考虑比较$i,j$两个位置的时候其实是找$a[i]&a[i+1],a[i+1]&a[i+2]$第一个不同的地方

所以每一段比较出来相同的位置的答案是一样的
随便乱做一下就完了

复杂度$O(n)$

#include<bits/stdc++.h>
using namespace std;
const int RLEN=1<<20|1;
inline char gc(){
    static char ibuf[RLEN],*ib,*ob;
    (ob==ib)&&(ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin));
    return (ob==ib)?EOF:*ib++;
}
#define gc getchar
inline int read(){
    char ch=gc();
    int res=0,f=1;
    while(!isdigit(ch))f^=ch=='-',ch=gc();
    while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=gc();
    return f?res:-res;
}
#define ll long long
#define re register
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define cs const
#define bg begin
#define poly vector<int>  
#define chemx(a,b) ((a)<(b)?(a)=(b):0)
#define chemn(a,b) ((a)>(b)?(a)=(b):0)
cs int N=1000005;
int n,p[N],ans[N],tot1,tot2;
char s[N];
int main(){
	n=read();
	scanf("%s",s+1);tot2=n;
	for(int i=1;i<=n;i++){
		if(s[i]>s[i+1])p[i]=1;
		else if(s[i]<s[i+1])p[i]=-1;
	}
	for(int i=1,pos=1;i<=n;i=pos+1,pos=i){
		while(!p[pos]&&pos<=n)pos++;
		if(pos>n){for(;i<=n;i++)ans[++tot1]=i;break;}
		if(p[pos]==-1)for(int j=pos;j>=i;j--)ans[tot2--]=j;
		else for(int j=i;j<=pos;j++)ans[++tot1]=j;
	}
	for(int i=1;i<=n;i++)cout<<ans[i]<<" ";
}