二刷提高课，题解目录在这里— 提高课的题解目录

由于题目是个环而且需要枚举断点的地方根据前面的经验我们想到了破环成链
但是这里并不是集合优化问题，而是询问当此点为起点是否可以通车
简单地N^2肯定不行必须是N所以我们需要看一下如何优化
可以发现无论我们选取哪个点所变动的莫过于此地的油量-到下一点耗费的量
我们可以发现当选某个点时只要后面的前缀和>=0则就可以通车
这不就是集合最值问题？我们使用单调队列来写
然后就是苦逼的边界问题┭┮﹏┭┮

#include<iostream>
using namespace std;
typedef long long ll;
const int N=2e6+10;
int a[N],b[N];
ll s[N];
int q[N];
int n;
bool st[N];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i]>>b[i];
    for(int i=1;i<=n;i++)s[i]=s[n+i]=a[i]-b[i];
    for(int i=1;i<=2*n;i++)s[i]+=s[i-1];
    //顺时针
    //当我们固定左端点时我们所寻找的是右边最小值故应该从后先前
    int hh=0,tt=0;
    q[0]=2*n+1;//用不到的点:边界问题
    for(int i=2*n;i>=0;i--)
    {
        while(hh<=tt&&i+n<q[hh])hh++;
        if(i<n)//因为我们只需要枚举1~N为起点即可（在后面最大值处理好的前提下）
        {
            if(s[i]<=s[q[hh]])st[i+1]=true;
            //注意前缀和选了i位意思其实我们选的是i+1位为起点
        }
        while(hh<=tt&&s[q[tt]]>=s[i])tt--;
        q[++tt]=i;
    }
    //逆时针，固定右端点所以是从小到大
    b[0]=b[n];
    hh=0,tt=0;
    q[0]=0;
    for(int i=1;i<=n;i++)s[i]=s[n+i]=a[i]-b[i-1];
    for(int i=1;i<=2*n;i++)s[i]+=s[i-1];
    for(int i=1;i<=n*2;i++)
    {
        while(hh<=tt&&i-n>q[hh])hh++;
        if(i>n)
        {
            if(s[i]>=s[q[hh]])st[i-n]=true;
            //注意我们枚举的右端点，左边只需要选最大的即可
            //所以这里的i是真实起点
        }
        while(hh<=tt&&s[q[tt]]<=s[i])tt--;
        q[++tt]=i;
    }
    for(int i=1;i<=n;i++)
    if(st[i])cout<<"TAK"<<endl;
    else cout<<"NIE"<<endl;
    return 0;
}