AcWing 1088. 旅行问题（前缀和 单调队列优化dp 破环成链 ）

#include<iostream>
#define int long long
using namespace std;
const int N=2e6+10;
int o[N],d[N],s[N],ok[N],n,q[N];
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>o[i]>>d[i],s[i]=s[i+n]=o[i]-d[i];
    for(int i=1;i<=2*n;i++)s[i]+=s[i-1];
    int hh=0,tt=-1;
    for(int i=2*n;i;i--){
        if(hh<=tt&&q[hh]>i+n-1)hh++;
        while(hh<=tt&&s[q[tt]]>=s[i])tt--;
        q[++tt]=i;
        if(i<=n&&s[q[hh]]>=s[i-1])ok[i]=1;
    }
    hh=0,tt=-1;
    d[0]=d[n];
    for(int i=1;i<=n;i++)s[i]=s[i+n]=o[i]-d[i-1];
    for(int i=2*n;i;i--)s[i]+=s[i+1];
    for(int i=1;i<=2*n;i++){
        if(hh<=tt&&q[hh]<i-n+1)hh++;
        while(hh<=tt&&s[q[tt]]>=s[i])tt--;
        q[++tt]=i;
        if(i>n&&s[i+1]<=s[q[hh]])ok[i-n]=1;
    }
    for(int i=1;i<=n;i++){
        ok[i]?puts("TAK"):puts("NIE");
    }
    
}
for(int i=1;i<=n;i++){
 ok[i]?puts(“TAK”):puts(“NIE”);
 }
}