[POI2014]KAR-Cards题解

Energy_Making · 2021-03-01 22:39:52 · 题解

1.前置知识

线段树

2.解法

这道题是一道线段树的连通性问题。而我们要维护的信息则也跟连通性有关——l 分别取正背面，r 能取到正面还是背面。

具体而言，我们把数字较小的一面记为 a，较大的一面记为 b。线段树中维护的信息即为 va：l 取 a 出发时 r 的最小值（显而易见的贪心思想）与 vb：l 取 b 出发时 r 的最小值。那么难点就在于维护 va 与 vb。这里放出 va 作为参考。

int mid=(l+r)>>1;
if(a[mid+1]>=node[p<<1].va)node[p].va=node[p<<1|1].va;
else if(b[mid+1]>=node[p<<1].va)node[p].va=node[p<<1|1].vb;
else node[p].va=inf;

首先我们都讨论了node[p<<1].va是因为 p 与 p 的左儿子起点 a 相同。

然后我们讨论a[mid+1]与b[mid+1]是因为要满足不下降的条件，注意先讨论较小的一项是因为要满足贪心原则（一个位置上的数合法时越小越有可能成功），如果两个都不行则用极大值标记为此路不通。

最后的 change 操作就将有改变的地方交换重新建树即可。

3.代码

#include<stdio.h>
#include<algorithm>
using namespace std;
const int inf=0x3f3f3f3f;
int n,m;
int a[200005],b[200005];
struct seg
{
    int l,r,va,vb;
    seg()
    {
        va=vb=inf;
    }
};
seg node[1000005];
void merge(int p,int l,int r)//精华所在
{
    int mid=(l+r)>>1;
    if(a[mid+1]>=node[p<<1].va)node[p].va=node[p<<1|1].va;
    else if(b[mid+1]>=node[p<<1].va)node[p].va=node[p<<1|1].vb;
    else node[p].va=inf;
    if(a[mid+1]>=node[p<<1].vb)node[p].vb=node[p<<1|1].va;
    else if(b[mid+1]>=node[p<<1].vb)node[p].vb=node[p<<1|1].vb;
    else node[p].vb=inf;
    //vb操作与va同理。
}
void build(int p,int l,int r)//常规操作
{
    node[p].l=l;
    node[p].r=r;
    if(l==r)
    {
        node[p].va=a[l];
        node[p].vb=b[l];
        return;
    }
    int mid=(l+r)>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
    merge(p,l,r);
}
void change(int p,int l,int r,int x)//相比于build，只是没有赋l与r的值，再加了个范围判断。
{
    if(l==r)
    {
        node[p].va=a[l];
        node[p].vb=b[l];
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid)change(p<<1,l,mid,x);
    else change(p<<1|1,mid+1,r,x);
    merge(p,l,r);
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        int x,y;
        scanf("%d %d",&x,&y);
        a[i]=min(x,y);
        b[i]=max(x,y);
    }
    build(1,1,n);
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d %d",&x,&y);
        swap(a[x],a[y]);
        swap(b[x],b[y]);
        change(1,1,n,x);
        change(1,1,n,y);
        if(node[1].va==inf&&node[1].vb==inf)printf("NIE\n");
        else printf("TAK\n");
    }
    return 0;
}