P3422题解

luogu_gza · 2023-09-16 21:42:25 · 题解

智商不够，数据结构来凑。

发现题目需要满足的就是

这个东西就很好维护了，枚举 s_i，然后套个不带修改的线段树即可。

注意，两个方向都要建一遍线段树，所以我封装了一下。

我觉得这东西 zkw 也可以维护，代码甚至短一截。

广告

Code:

// Problem: P3422 [POI2005] LOT-A Journey to Mars
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3422
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define MT int TTT=R;while(TTT--)
#define pc putchar
#define R read()
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define rep(i,a,b) for(int i=a;i>=b;i--)
#define m1(a,b) memset(a,b,sizeof a)
namespace IO
{
    inline int read()
    {
        int x=0;
        char ch=getchar();
        bool f=0;
        while(!isdigit(ch)){if(ch=='-') f=1;ch=getchar();}
        while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
        if(f) x=-x;
        return x;    
    }
    template<typename T> inline void write(T x)
    {
        if(x<0)
        {
            pc('-');
            x=-x;
        }
        if(x>9) write(x/10);
        pc(x%10+'0');
    }
};
namespace math
{
    inline int gcd(int a,int b)
    {
        return b?gcd(b,a%b):a;
    }
    inline int qmi(int a,int b,int p)
    {
        int res=1;
        while(b)
        {
            if(b&1) res=res*a%p;
            a=a*a%p;
            b>>=1;
        }
        return res;
    }
    inline int inv(int a,int p)
    {
        return qmi(a,p-2,p);
    }
    const int MAXN=2e6+10;
    int my_fac[MAXN],my_inv[MAXN];
    void init_binom(int mod)
    {
        my_fac[0]=1;fo(i,1,min(MAXN,mod)-1) my_fac[i]=my_fac[i-1]*i%mod;
        my_inv[min(MAXN,mod)-1]=qmi(my_fac[min(MAXN,mod)-1],mod-2,mod);rep(i,min(MAXN,mod)-2,0) my_inv[i]=my_inv[i+1]*(i+1)%mod;
    }
    int binom(int a,int b,int mod)
    {
        return my_fac[a]*my_inv[b]%mod*my_inv[a-b]%mod;
    }
}
using namespace IO;
using namespace math;

#define now tr[u]
#define ls tr[u<<1]
#define rs tr[u<<1|1]
const int N=1e6+10;
int n;
int p[N],d[N],s[N],S[N];
struct SegmentTree{
    struct Node{
        int l,r,d;
    }tr[N<<2];
    void pushup(int u)
    {
        now.d=min(ls.d,rs.d);
    }
    void build(int u,int l,int r,int typ)
    {
        if(l==r) tr[u]={l,r,typ==1?s[l]:S[l]};
        else
        {
            tr[u]={l,r};
            int mid=l+r>>1;
            build(u<<1,l,mid,typ),build(u<<1|1,mid+1,r,typ);
            pushup(u);
        }
    }
    int query(int u,int l,int r)
    {
        if(tr[u].l==l&&tr[u].r==r) return tr[u].d;
        else
        {
            int mid=now.l+now.r>>1;
            if(r<=mid) return query(u<<1,l,r);
            else if(l>mid) return query(u<<1|1,l,r);
            else return min(query(u<<1,l,mid),query(u<<1|1,mid+1,r));
        }
    }
}tr1,tr2;
signed main(){
    n=R;
    fo(i,1,n) p[i]=R,d[i]=R,s[i]=s[i-1]+p[i]-d[i];
    fo(i,n+1,2*n) s[i]=s[i-1]+p[i-n]-d[i-n];
    fo(i,1,n-1) S[i]=S[i-1]+p[n-i+1]-d[n-i];
    S[n]=S[n-1]+p[1]-d[n];
    fo(i,n+1,2*n-1) S[i]=S[i-1]+p[2*n-i+1]-d[2*n-i];
    tr1.build(1,1,n*2-1,1);
    tr2.build(1,1,n*2-1,2);
    fo(i,1,n)
    {
        if(tr1.query(1,i,i+n-1)>=s[i-1]) puts("TAK");
        else if(tr2.query(1,n-i+1,2*n-i)>=S[n-i]) puts("TAK");
        else puts("NIE");
    }
}