本文共 1089 字，大约阅读时间需要 3 分钟。
这题给的时限是10S，且数据量不大，可以O（n*(n+m)）大概2e9 过。。。
**O（n3）优化到O（n2）用到了dp预处理
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #define MAXN 1000005 9 using namespace std;10 typedef long long ll;11 int a[100005];12 struct Edg{13 int l,r;14 int num,v;15 }e[10005];16 int b[100005],xor1[1000005];17 int main()18 { int n,m;19 20 scanf("%d%d",&n,&m);21 for(int i=1;i<=n;i++)22 {23 scanf("%d",&a[i]);24 }25 xor1[0]=0;26 for(int i=1;i<=1000000;i++)27 {28 xor1[i]=xor1[i-1]^i;29 }30 31 for(int i=1;i<=m;i++)32 {33 scanf("%d%d",&e[i].l,&e[i].r);34 e[i].num=i,e[i].v=0;35 }36 37 int res;38 for(int i=1;i<=n;i++)39 {40 for(int j=i;j<=n;j++)41 {42 res=xor1[a[i]]^xor1[a[j]]^min(a[i],a[j]);43 if(j==i) b[j]=res;44 else b[j]=max(res,b[j-1]);45 }46 for(int k=1;k<=m;k++)47 { if(e[k].l<=i&&i<=e[k].r)48 {49 e[k].v=max(e[k].v,b[e[k].r]);50 }51 52 }53 }54 for(int k=1;k<=m;k++)55 {56 printf("%d\n",e[k].v);57 }58 return 0;59 }
转载于:https://www.cnblogs.com/lnu161403214/p/8605250.html
