CF286C Main Sequence

栈真是和括号完美结合的数据结构呢

看到此题中的括号一词，我们不难想到栈这个东西

因为有左括号，则必有右括号

因为后扫到的左括号先和右括号匹配，所以可以用栈维护

那么我们就从右边开始向左边扫，扫到一个位置不能和栈顶元素匹配或者已经被钦定为右括号，就把他丢进右括号的栈里

为什么从右边开始扫呢？

因为题目给出的是钦定的右括号，也就是说这些位置一定是右括号

如果从左边开始则不能很好的满足这些数是右括号的条件

所以从右边开始贪心即可

若扫到的元素不能和栈顶元素匹配，如果把它和别的元素匹配，就会导致一个括号被忽略的情况，所以不能和栈顶匀速匹配就进栈

方案的话如果是右括号就是$-$，左括号就是$+$

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define int long long
int n,m,top=0;
int a[2000050],stack[2000050],b[2000050],answer[2000050];
signed main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    scanf("%lld",&m);
    int x;
    for(int i=1;i<=m;i++)scanf("%lld",&x),b[x]=1;
    for(int i=n;i>=1;i--)
    {
        if(a[i]!=stack[top] || b[i]==1)stack[++top]=a[i],answer[i]=-1;
        else top--,answer[i]=1;
    }
    if(top)printf("NO");
    if(!top)printf("YES\n");
    if(!top)for(int i=1;i<=n;i++)printf("%lld ",answer[i]*a[i]);
    return 0;
}