$\huge \color{orange}{成魔之路->}$ $\huge \color{purple}{算法提高课题解}$

顺时针思路：

1. s[i] 是 oil[i] 和 dist[i] 差值的前缀和
2. 找到区间 [i,i + n - 1] 中的最小值 s[j]，若 s[j] >= s[i - 1],则 st[i] = true
3. 利用单调队列找到长度不超过 n 的最小值
4. 逆时针就是找长度不超过 n 的最大值，其他可参考顺时针进行推断

完整代码

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 2e6 + 10;

int n;
int oil[N],dist[N];
LL s[N];
int q[N];
bool st[N];

int main()
{
    cin>>n;

    for(int i=1;i<=n;i++) cin>>oil[i]>>dist[i];

    //顺时针
    for(int i=1;i<=n;i++) s[i]=s[i+n]=oil[i]-dist[i];
    for(int i=1;i<=n*2;i++) s[i]+=s[i-1];
    int hh=0,tt=0;
    q[0]=n*2+1;
    for(int i=n*2;i>=0;i--)
    {
        if(q[hh]>i+n) hh++; //队头出列
        if(i<n&&s[i]<=s[q[hh]]) st[i+1]=true; //严格单调递增，队头即最小值
        while(hh<=tt&&s[q[tt]]>=s[i]) tt--;
        q[++tt]=i;
    }

    //逆时针
    dist[0]=dist[n];
    for(int i=1;i<=n;i++) s[i]=s[i+n]=oil[i]-dist[i-1];
    for(int i=1;i<=2*n;i++) s[i]+=s[i-1];
    hh=0,tt=0,q[0]=0;
    for(int i=1;i<=n*2;i++)
    {
        if(q[hh]<i-n) hh++;
        if(i>n&&s[i]>=s[q[hh]]) st[i-n]=true; //严格单调递减，队头即最大值
        while(hh<=tt&&s[q[tt]]<=s[i]) tt--;
        q[++tt]=i;
    }

    for(int i=1;i<=n;i++) 
        if(st[i]) puts("TAK");
        else puts("NIE");

    return 0;
}