e
好吧我再自己去找找错误
by _int_me @ 2018-11-04 17:01:07
恩总算知道了是st表查询有问题 没事了
by _int_me @ 2018-11-04 17:30:40
此题用st表完全可以nlogn啊
by Pbri @ 2019-06-25 12:45:57
@[Three_body](/space/show?uid=151366) 求问nlogn做法，我写的好像是O（n）~O（n2）但是没有被卡QWQ
```cpp
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
const int maxn=2e5+10;
int n,num_color,p,ans;
int lg[maxn];
int st[maxn][51];
struct node
{
int color,w;
}a[maxn];
vector<int>sum_color[51];
void ST()
{
lg[0]=-1;
for(int i=1;i<=n;i++)
{
lg[i]=lg[i/2]+1;
st[i][0]=a[i].w;
}
for(int j=1;j<=lg[n];j++)
for(int i=1;i+(1<<j)-1<=n;i++)
st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
}
int MIN(int x,int y)
{
if(x>y) swap(x,y);
int l=lg[y-x+1];
return min( st[x][l] , st[y-(1<<l)+1][l] );
}
int main()
{
scanf("%d%d%d",&n,&num_color,&p);
for(int i=1;i<=n;i++) scanf("%d%d",&a[i].color,&a[i].w);
ST();
for(int i=1;i<=n;i++)
{
int k=a[i].color;
if(!sum_color[k].empty())
{
for(int j=sum_color[k].size()-1;j>=0;j--)
if(MIN(i,sum_color[k][j])<=p)
{
ans=ans+j+1;
break;
}
}
sum_color[k].push_back(i);
}
printf("%d",ans);
return 0;
}
```
by 做梦都想AK @ 2019-10-11 14:33:01
@[做梦都想AK](/space/show?uid=101528) 我写了博客：https://www.luogu.org/blog/rubik-aoyi715103/p1311-jing-yan-zong-jie-rmq
by Pbri @ 2019-10-12 12:32:47