洛谷P3948 数据结构—

题目传送

感觉这道题秀了我一地的智商。。。

审题没审好，没确定带修改的操作中询问的次数<=1000，且max和min都是事先给好、不变的。想了半天线段树、分块，却忘了最基础的暴力。

写不出题时先写暴力。

先考虑在线的部分的做法：

　　因为修改的次数多，询问的次数少，而且询问很难在在线的情况下优化了，又发现数据随机，如果询问暴力处理的话最差复杂度也只有O（1000*n），在随机数据下复杂度远比此低。于是可以用差分优化区间加，询问暴力做就行。

离线部分：

　　显然不能暴力处理询问了，但是没有修改，又是区间询问个数，自然要想到前缀和优化了。设sum[i]为前i位满足条件的个数，扫一遍就能处理出sum，这是就能O(1)做询问了。

代码：

 #include<iostream>

 #include<cstdio>

 using namespace std;

 const int N=;

 int n,opt,minn,maxx,fin,X;

 int x,sum[N];

 long long d[N],now,t,mod;

 char ch;

 bool f;

 inline int read()

 {

     x=;

     f=;

     ch=getchar();

     while(!isdigit(ch)) f|=(ch=='-'),ch=getchar();

     while(isdigit(ch)) x=(x<<)+(x<<)+(ch^),ch=getchar();

     return f?-x:x;

 }

 inline char mygetchar()

 {

     ch=getchar();

     while(ch!='A'&&ch!='Q')

         ch=getchar();

     return ch;

 }

 void print(int a)

 {

     if(a>)

         print(a/);

     putchar(a%+'');

 }

 int main()

 {

 //    freopen("my.out","w",stdout);

     n=read(),opt=read(),mod=read(),minn=read(),maxx=read();

     char cao;

     int l,r;

     for(int i=;i<=opt;++i)

     {

         cao=mygetchar();

         if(cao=='A')

         {

             l=read(),r=read(),X=read();

             d[l]+=X;

             d[r+]-=X;

         }

         else

         {

             l=read(),r=read();

             int ans=,j;

             now=;

             for(j=;j<l;++j)

                 now+=d[j];

             for(j=l;j<=r;++j)

             {

                 now+=d[j];

                 t=now%mod*j%mod;

                 if(t>=minn&&t<=maxx)

                     ans++;

             }

             print(ans);

             putchar('\n');

         }

     }

     fin=read();

     now=;

     for(int i=;i<=n;++i)

     {

         now+=d[i];

         t=now%mod*i%mod;

         sum[i]=sum[i-]+(t>=minn&t<=maxx);

     }

     for(int i=;i<=fin;++i)

     {

         l=read(),r=read();

         print(sum[r]-sum[l-]);

         putchar('\n');

     }

     return ;

 }

总结：写不出题想想暴力（没准就是正解呢）

　　差分多用于优化离线的区间修改。

　　前缀和多用于离线的区间查询。

巴特西

洛谷P3948 数据结构——题解

最新文章

热门文章