题目链接：http://codeforces.com/contest/1154/problem/E
题意：两个人轮流取最大值与旁边k个数，问最后这所有的数分别被谁给取走了
分析：看这道题一点思路都没有，想不到模拟链表也该能想到线段树的啊
大部分AC代码是模拟链表的，写起来也更快，但我线段树很不熟，线段树的代码也写一份吧
另外，以后要养成一种习惯，除了主函数定义int main里有int外，其他地方统一用ll了，不要自己给自己挖坑。。。。。
线段树：
意识到是线段树后我建树部分就拿不准怎么做，事实上可以一开始先输入在数组里，建树部分代码稍微改动一下就好
代码本身不难，就着注释读一读很明显，要注意的部分我也提到了
这次的模板我是用的CF大佬的，感觉很好用
然后快读和快写效果十分显著，直接从102ms变成了62ms
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int inf=1<<30; const int maxn=2*1e5+7; const double pi=acos(-1); const int mod=1e9+7; int a[maxn],ans[maxn],pre[maxn],nxt[maxn],pos[maxn]; struct node { int l,r,sum,lazy; }tree[4*maxn]; inline ll read(){ ll x=0,tmp=1; char ch=getchar(); while(!isdigit(ch)){ if(ch=='-') tmp=-1; ch=getchar(); } while(isdigit(ch)){ x=(x<<3)+(x<<1)+ch-48; ch=getchar(); } return tmp*x; } inline void write(ll x){ ll y=10,len=1; while(y<=x){ y=(y<<3)+(y<<1); len++; } while(len--){ y/=10; putchar(x/y+48); x%=y; } } inline void pushdown(ll p){ if(tree[p].lazy){ tree[p<<1].sum=0; tree[p<<1].lazy=1; tree[p<<1|1].sum=0; tree[p<<1|1].lazy=1; tree[p].lazy=0; } } void build(ll p,ll l,ll r){ tree[p].l=l; tree[p].r=r; if(l==r){ tree[p].sum=a[l]; return; } ll mid=(l+r)>>1; build(p<<1,l,mid); build(p<<1|1,mid+1,r); tree[p].sum=max(tree[p<<1].sum,tree[p<<1|1].sum); } void update(ll p,ll l,ll r){ if(l<=tree[p].l&&tree[p].r<=r){ tree[p].sum=0; tree[p].lazy=1; return; } pushdown(p); ll mid=(tree[p].l+tree[p].r)>>1; if(l<=mid) update(p<<1,l,r); if(r>mid) update(p<<1|1,l,r); tree[p].sum=max(tree[p<<1].sum,tree[p<<1|1].sum); } ll query(ll p,ll l,ll r){ if(l<=tree[p].l&&tree[p].r<=r) return tree[p].sum; pushdown(p); ll mid=(tree[p].l+tree[p].r)>>1,ans=0; if(l<=mid) ans=max(ans,query(p<<1,l,r)); if(r>mid) ans=max(ans,query(p<<1|1,l,r)); tree[p].sum=max(tree[p<<1].sum,tree[p<<1|1].sum); return ans; } int main(){ ll n,k;scanf("%I64d%I64d",&n,&k); nxt[0]=1,pre[n+1]=n;//这点要注意别忘了 for(ll i=1;i<=n;i++){ a[i]=read(); pos[a[i]]=i; pre[i]=i-1; nxt[i]=i+1;//咋一看似乎没必要，但取走操作之后可能第5个人的前一个人就不是第四个人而是第二个人了 } build(1,1,n); ll now=0;//这个now是第几组的意思，弄成0,1方便异或更改 while(1){ ll x=query(1,1,n); if(x<=0) break; ans[pos[x]]=now; ll l=pos[x],r=pos[x]; for(ll i=1;i<=k;i++){ if(pre[l]==0) break; else { l=pre[l]; ans[l]=now; } } for(ll i=1;i<=k;i++){ if(nxt[r]==n+1) break; else{ r=nxt[r]; ans[r]=now; } } update(1,l,r); pre[nxt[r]]=pre[l]; nxt[pre[l]]=nxt[r];//这个更新很灵性吧，就是把最右边的前一位更改为最左边的前一位，最左边的后一位 //更改为最右边的后一位，也就是把中间被选走的数的影响给剔除，也是nxt和pre数组的意义所在 now^=1; } for(int i=1;i<=n;i++)write(ans[i]+1); putchar(' '); return 0; }
模拟链表:
就是用两个优先队列来模拟链表，优先队列内的数是按顺序从大到小存好的，刚好满足要求
看懂了线段树看这个肯定没有一点问题：
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int inf=1<<30; const int maxn=2*1e5+7; const double pi=acos(-1); const int mod=1e9+7; typedef pair<int,int> P; int pre[maxn],nxt[maxn],a[maxn],ans[maxn]; priority_queue<P> p,q; int main(){ int n,k;scanf("%d%d",&n,&k); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); pre[i]=i-1,nxt[i]=i+1; q.push(P(a[i],i)); } int opt=0; while(!q.empty()){ while(p.size()&&q.top()==p.top()) q.pop(),p.pop(); if(q.empty()) break; int m,i,j; //求前缀 for(i=pre[q.top().second],j=1;j<=k&&i;j++,i=pre[i]){ p.push(P(a[i],i)); ans[i]=opt+1; } for(m=nxt[q.top().second],j=1;j<=k&&m;j++,m=nxt[m]){ p.push(P(a[m],m)); ans[m]=opt+1; } ans[q.top().second]=opt+1;q.pop(); opt^=1; nxt[i]=m,pre[m]=i; } for(int i=1;i<=n;i++)cout<<ans[i]; cout<<endl; return 0; }