F,G题解
F贪心的题目要求大于2的子数组就行,于是贪心地考虑长为3的回文数组,那这是一个什么形式呢?a+b+a或者a+a+a,我们只需要记住每一个l对应的最左端的r的位置就行,可以考虑用双指针来解题。具体而言,我们可以开一个哈希表存储数字数组,枚举到当前位置right,查看前方最左边的数字的位置left,是否满足right-left>=2。
import collections from sys import stdin input=lambda:stdin.readline().strip() n,q=map(int,input().split()) A=list(map(int,input().split())) dic=collections.defaultdict(collections.deque) left=0 right=0 dp=[float('inf')]*n while right<n: if len(dic[A[right]])<1: dic[A[right]].append(right) else: while dic[A[right]] and dic[A[right]][0]<left: dic[A[right]].popleft() while dic[A[right]] and right-dic[A[right]][0]>=2 and left<=dic[A[right]][0]: dp[left]=right if left==dic[A[right]][0]: dic[A[right]].popleft() left+=1 dic[A[right]].append(right) right+=1 for i in range(q): l,r=map(int,input().split()) l-=1 r-=1 if r>=dp[l]: print("YES") else: print("NO")
统计逆序队的方法有两个,一个是归并排序,一个是树状数组,这题我们采用树状数组,从前往后进行一遍,统计当前数字对前面数字的贡献dp,从后往前进行一边,统计当前数字对后面数字的贡献dp2,再用双指针统计每一段l,r是否满足题意。还要再开一个dp3统计在l,r这段的逆序对数量。
from sys import stdin input=lambda:stdin.readline().strip() n,k=map(int,input().split()) A=list(map(int,input().split())) def low_bit(x): return x&(-x) def SUM(node,index): ret=0 while index>0: ret+=node[index] index-=low_bit(index) return ret def add(node,index,x,n): while index<n: node[index]+=x index+=low_bit(index) ret=0 N=max(A)+1 node=[0]*N dp=[0]*(n+1) node2=[0]*N for i in range(n): dp[i+1]=SUM(node,N-1)-SUM(node,A[i]) ret+=dp[i+1] add(node,A[i],1,N) dp2=[0]*(n+2) for i in range(n,0,-1): dp2[i]=SUM(node2,A[i-1]-1) add(node2,A[i-1],1,N) node3=[0]*N left=1 right=1 if ret<k: print(0) else: res=1 A=[0]+A while right<=n: x=A[right] ret-=dp[right] ret-=dp2[right] ret+=SUM(node3,N-1)-SUM(node3,x) add(node3,x,1,N) right+=1 while ret<k: ret+=dp[left] ret+=dp2[left] ret-=SUM(node3,A[left]-1) add(node3,A[left],-1,N) left+=1 res+=right-left print(res)