P3422

一道有点意思的题。

看到是一个环，先破环为链，即 $a_{n+i}=a_i, b_{n+i}=b_i$，此时就只需要跳到 $x+n$ 而无需判环了。

如果顺时针走：

令 $sum_i = \sum\limits_{j=1}^{i}{a_j-b_j}$，当能从 $x$ 跳到 $x+n$ 时，有

$$sum_{x-1} \le sum_x, sum_{x-1} \le sum_{x+1}, \dots, sum_{x-1} \le sum_{x+n-1}$$

变形一下：

$$sum_{x-1} \le \min\limits_{x \le i < x+n}\{sum_i\}$$

求长度不变区间的最小值，可以使用单调队列。

逆时针就反着再做一遍。

代码：

#include<bits/stdc++.h>

using ll = long long;
using pii = std::pair<int, int>;

const int N = 1e6 + 5;
int n, hd, tl; 
int a[N << 1], b[N << 1], c[N << 1], q[N << 1];
int ta[N], tb[N], ans[N], flag[N];
ll s[N << 1];

void solve() {
	for (int i = 1; i <= n; i++) s[i] = s[i - 1] + c[i];
	for (int i = 1; i <= n; i++) s[i + n] = s[i + n - 1] + c[i];
	for (int i = 1, hd = 1, tl = 0; i <= n * 2; i++) {
		if (hd <= tl && q[hd] < i - n + 1) hd++;
		while (hd <= tl && s[q[tl]] >= s[i]) tl--;
		q[++tl] = i;
		if (i >= n)
			ans[i - n + 1] = s[q[hd]];
	}
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cin >> n;
	for (int i = 1; i <= n; i++) {
		std::cin >> a[i] >> b[i];
		a[i + n] = a[i], b[i + n] = b[i];
		c[i + n] = c[i] = a[i] - b[i];
	}
	solve();
	for (int i = 1; i <= n; i++)
		if (ans[i] >= s[i - 1])
			flag[i] = 1;
	for (int i = 1; i <= n; i++)
		c[i] = a[n - i + 1] - b[((n - i ? n - i : n))];
	solve();
	for (int i = 1; i <= n; i++)
		if (ans[i] >= s[i - 1])
			flag[n - i + 1] = 1;
	for (int i = 1; i <= n; i++)
		std::cout << (flag[i] ? "TAK" : "NIE") << "\n";
	return 0;
}

#include<bits/stdc++.h>
using namespace std;  
typedef long long LL;  
const int N=2000005;
LL sum[N],p[N],d[N],q[N],ok[N],n;
template<typename T> void read(T& x)
{
    x=0;char c=getchar();int f=1;
    for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
    for(; isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
    x=x*f;
}
void DP1()
{
	
	int l=1,r=0;
	for (int i=1; i<=n; ++i){
		while (l<=r && sum[q[r]]>=sum[i]) --r;
		q[++r]=i;
	}
	/*
	思路：当前枚举到i，点(i-n)和i是同个点，那么研究 (i-n)->i能否顺利一圈。
	判断方法：只要 sum[i-n+1]~sum[i]的 任意一个都大于等于sum[i-n]即可
	 sum[i-n+1]~sum[i]中的最小值是sum[q[l]]，所以只要判断 sum[q[l]]>=sum[i-n]即可证明。 
	*/ 
	for (int i=n+1; i<=n*2; ++i){
		while (l<=r && sum[q[r]]>=sum[i]) --r;
		q[++r]=i;
		while (l<=r && q[l]<=i-n) ++l;
		if(sum[q[l]]-sum[i-n]>=0) ok[i-n]=1;	
	}
}
void DP2()
{
	int l=1,r=0;
	for (int i=n*2; i>n; --i){
		while(l<=r && sum[q[r]]>=sum[i]) --r;
		q[++r]=i;
	}
	for (int i=n; i; --i){
		while(l<=r && sum[q[r]]>=sum[i]) --r;
		q[++r]=i;
		while(l<=r && q[l]>=i+n) ++l;
		if (sum[q[l]]-sum[i+n]>=0) ok[i]=1;		
	}
}
int main()  
{  
 	read(n);
 	sum[0]=p[0]=d[0]=0;
 	for (int i=1; i<=n; ++i)
	 {
		read(p[i]);p[i+n]=p[i];
		read(d[i]);d[i+n]=d[i];
		sum[i]=sum[i-1]+p[i-1]-d[i-1];
 	}
 	for (int i=n+1; i<=n*2; ++i)sum[i]=sum[i-1]+p[i-1]-d[i-1];
 	//sum[i]表示达到i点的汽油存量 
 	DP1();
 	
 	for (int i=n*2; i; --i) sum[i]=sum[i+1]+p[i+1]-d[i];
 	DP2();
 	
 	for (int i=1; i<=n; ++i) printf("%s\n",ok[i]?"TAK":"NIE");
 	return 0;
}