算法1

• 先考虑暴力怎么做：首先拆环为链。对于每个车站，我们设a[i]=p[i]-d[i]，处理出a[i]的前缀和，问题就变成了枚举起点i，判断在经过的车站中是否存在一个车站j，使得sum[j]-sum[i]<0，如果是，那么就不合法。容易发现这个算法的时间复杂度是O(n2)的。
• 考虑优化：我们将上面的式子移项：sum[j]<sum[i]，于是问题就转化为了判断对于每一个起点i，其经过车站中sum[j]的最小值是否小于sum[i]。因此我们可以用一个单调队列来维护一个前缀和的最小值，走到队首对应的终点时弹出队首并记为合法，弹出队尾时记为不合法，时间复杂度降低到了O(n)。
  

时间复杂度 O(n)

数据范围
3≤ n ≤ 10^6
0≤ pi≤ 2×10^9
0< di ≤ 2×10^9

所以 可以这样玩一玩 所以 可以这样玩一玩

C++ 代码

#include<bits/stdc++.h>
using namespace std;
#define N 2000010
#define LL long long
int n,l,r,a[N],b[N],c[N],ans[N][2];
LL sum[N][2];
struct node{
    int pos;
    LL val;
}q[N];
int main(){
    scanf("%d",&n);int m=n<<1;
    for(int i=1;i<=n;i++){scanf("%d%d",&a[i],&b[i]);a[i+n]=a[i];b[i+n]=b[i];c[i]=c[i+n]=b[i-1];}
    c[1]=c[n+1]=b[n];
    for(int i=1;i<=m;i++) sum[i][0]=sum[i-1][0]+a[i]-b[i];
    for(int i=m;i>=1;i--) sum[i][1]=sum[i+1][1]+a[i]-c[i];
    l=r=1;q[l]=(node){0,0};
    for(int i=1;i<=m;i++){
        while(l<=r&&q[l].pos+n+1<=i){ans[q[l++].pos+1][0]=0;}
        while(l<=r&&q[r].val> sum[i][0]){ans[q[r--].pos+1][0]=1;}
        q[++r]=(node){i,sum[i][0]};
    }
    l=r=1;q[r]=(node){m+1,0};
    for(int i=m;i>=1;i--){
        while(l<=r&&q[l].pos-n-1>=i){ans[q[l++].pos-1][1]=0;}
        while(l<=r&&q[r].val> sum[i][1]){ans[q[r--].pos-1][1]=1;}
        q[++r]=(node){i,sum[i][1]};
    }
    for(int i=1;i<=n;i++){
        if(ans[i][0]&ans[i+n][1]) puts("NIE");
        else puts("TAK");
    }
    return 0;
}