題意：

給你一個(gè)長(zhǎng)為$n$的數(shù)字串，有正數(shù)和負(fù)數(shù)，和$m$個(gè)詢問(wèn)。每個(gè)詢問(wèn)詢問(wèn)你區(qū)間$[L,R]$中權(quán)值和小于$U$的子區(qū)間中權(quán)值和最大是多少。

$n<=2000,m<=200000$

可以發(fā)現(xiàn)，n很小，m較大，因此，我們可以先預(yù)處理出來(lái)所有子區(qū)間的和，然后將子區(qū)間按照權(quán)值和從小到大排序。然后我們對(duì)整個(gè)串進(jìn)行分塊。

對(duì)于每一個(gè)塊，我們利用樹(shù)狀數(shù)組維護(hù)以這個(gè)塊中的某個(gè)點(diǎn)為左端點(diǎn)的區(qū)間的最大值。對(duì)于塊中的每個(gè)位置，我們利用樹(shù)狀數(shù)組維護(hù)以他為左端點(diǎn)的區(qū)間的最大值。

之后我們將詢問(wèn)也從小到大排列，將所有樹(shù)狀數(shù)組的初始值都賦為-inf。之后我們每計(jì)算一個(gè)詢問(wèn)，就把新的合法的序列放進(jìn)對(duì)應(yīng)的塊的樹(shù)狀數(shù)組里以及他左端點(diǎn)的樹(shù)狀數(shù)組里。

詢問(wèn)的時(shí)候，對(duì)于整個(gè)塊位于區(qū)間內(nèi)的，查詢塊的樹(shù)狀數(shù)組的前綴最大值，否則便利位置，查每個(gè)位置樹(shù)狀數(shù)組的前綴最大值。

  1 #include<iostream>
  2 #include<cstdlib>
  3 #include<cstdio>
  4 #include<cstring>
  5 #include<algorithm>
  6 #include<queue>
  7 #define N 2005
  8 #define M 200005
  9 #include<cmath>
 10 #define lowbit(i) (i&(-i))
 11 using namespace std;
 12 int n,m;
 13 int A[N];
 14 typedef pair<long long,pair<int,int>> T;
 15 long long ans[M];
 16 struct no{
 17     int l,r,bh;
 18     long long data;
 19 }q[M];
 20 priority_queue<T,vector<T>,greater<T > > q1;
 21 int len,bel[N];
 22 int st[N];
 23 long long B[N][N];
 24 long long C[N][N];
 25 bool cmp(const no &a,const no &b)
 26 {
 27     return a.data<b.data;    
 28 }
 29 void add1(int x,int y,long long data)
 30 {
 31     for(int i=y;i<=n;i =lowbit(i))
 32     {
 33         B[x][i]=max(B[x][i],data);
 34     }
 35 }
 36 void add2(int x,int y,long long data)
 37 {
 38     for(int i=y;i<=n;i =lowbit(i))
 39     {
 40         C[x][i]=max(C[x][i],data);
 41     }
 42 }
 43 long long get1(int x,int y)
 44 {
 45     long long ans=-1e17;
 46     for(int i=y;i;i-=lowbit(i))
 47     {
 48         ans=max(ans,B[x][i]);
 49     }
 50     return ans;
 51 }
 52 long long get2(int x,int y)
 53 {
 54     long long ans=-1e17;
 55     for(int i=y;i;i-=lowbit(i))
 56     {
 57         ans=max(ans,C[x][i]);
 58     }
 59     return ans;
 60 }
 61 long long que(int l,int r)
 62 {
 63     if(bel[l]==bel[r])
 64     {
 65         long long ans=-1e17;
 66         for(int i=l;i<=r;i  )
 67         {
 68             ans=max(ans,get1(i,r));
 69         }
 70         return ans;
 71     }
 72     long long ans=-1e17;
 73     for(int i=l;i<st[bel[l] 1];i  )
 74     {
 75         ans=max(ans,get1(i,r));
 76     }
 77     for(int i=bel[l] 1;i<bel[r];i  ) ans=max(ans,get2(i,r));
 78     for(int i=st[bel[r]];i<=r;i  )
 79     {
 80         ans=max(ans,get1(i,r));
 81     }
 82     return ans;
 83 }
 84 int main()
 85 {
 86     scanf("%d%d",&n,&m);
 87     for(int i=1;i<=n;i  )
 88     {
 89         scanf("%d",&A[i]);
 90     }
 91     len=sqrt(n);
 92     for(int i=1;i<=n;i  )
 93     {
 94         bel[i]=(i-1)/len 1;
 95         if(!st[bel[i]])st[bel[i]]=i;
 96     }
 97     for(int i=1;i<=n;i  )
 98     {
 99         for(int j=0;j<=n;j  ) B[i][j]=C[i][j]=-1e17;
100     }
101     bel[n 1]=bel[n] 1;
102     st[bel[n 1]]=n 1;
103     for(int i=1;i<=n;i  )
104     {
105         long long ans=0;
106         for(int j=i;j<=n;j  )
107         {
108             ans =A[j];
109             T x;
110             x.first=ans;
111             x.second.first=i;
112             x.second.second=j;
113             q1.push(x);
114         }
115     }
116     for(int i=1;i<=m;i  )
117     {
118         scanf("%d%d%lld",&q[i].l,&q[i].r,&q[i].data);
119         q[i].bh=i;
120     }
121     sort(q 1,q m 1,cmp);
122     for(int i=1;i<=m;i  )
123     {
124         while(!q1.empty()&&q1.top().first<=q[i].data)
125         {
126             T x=q1.top();q1.pop();
127             add1(x.second.first,x.second.second,x.first);
128             add2(bel[x.second.first],x.second.second,x.first);
129         }
130         ans[q[i].bh]=que(q[i].l,q[i].r);
131     }
132     for(int i=1;i<=m;i  )
133     {
134         if(ans[i]==-1e17)
135             printf("NONE\n");
136         else printf("%lld\n",ans[i]);
137     }
138     return 0;
139 }
140 /*
141 2 1
142 10000000000000000 -10000000000000000
143 */ 

?