心态爆炸，打出gg。。。

A 爆long long fst了，B看错题半天然后又写挂一个细节

原地爆炸，差点炸出div1了qwq

A.

考虑枚举走了几个完整段，分情况讨论一下

然后就是一个gcd

注意写的不好可能会爆long long

1 #include
      
        2 #define ll long long 3 using namespace std; 4 ll n,k,a,b; 5 ll gcd(ll a,ll b) 6 { 7     if(!b)return a; 8     return gcd(b,a%b); 9 }10 int main()11 {12     cin>>n>>k>>a>>b;13     ll x=n*k,y=0;14     for(int i=1;i<=n;++i)15     {16         x=min(x,n*k/gcd(a+b+k*i,n*k));17         y=max(y,n*k/gcd(a+b+k*i,n*k));18         x=min(x,n*k/gcd(a-b+k*i,n*k));19         y=max(y,n*k/gcd(a-b+k*i,n*k));20         x=min(x,n*k/gcd(b-a+k*i,n*k));21         y=max(y,n*k/gcd(b-a+k*i,n*k));22         x=min(x,n*k/gcd(k-a-b+k*i,n*k));23         y=max(y,n*k/gcd(k-a-b+k*i,n*k));24     }25     cout<
       
        <<" "<
        
         <
        
       
      

B.

维护每个元素按排列循环走下去的下一个元素是什么

然后对每个左端点倍增出离他最近的右端点

然后倒着扫一下取个后缀min

每次询问看是否超过最近的右端点就行了

1 #include
      
        2 #define maxn 200005 3 using namespace std; 4 int n,m,q; 5 int p[maxn],a[maxn]; 6 int Ans[maxn]; 7 int to[maxn],nxt[maxn][22],lst[maxn]; 8 int minr[maxn]; 9 int main()10 {11     scanf("%d%d%d",&n,&m,&q);12     for(int i=1;i<=n;++i)scanf("%d",&p[i]);13     for(int i=1;i<=m;++i)scanf("%d",&a[i]);14     for(int i=1;i
       
        =1;--i)19     {20         nxt[i][0]=lst[to[a[i]]];21         lst[a[i]]=i;22     }23     for(int j=1;j<=19;++j)24         for(int i=1;i<=m+1;++i)nxt[i][j]=nxt[nxt[i][j-1]][j-1];25     for(int i=1;i<=m;++i)26     {27         int x=n-1,r=i;28         for(int j=19;j>=0;--j)if(x-(1<
        
         =0)x-=(1<
         
          =1;--i)minr[i]=min(minr[i],minr[i+1]);32     for(int i=1;i<=q;++i)33     {34         int l,r;35         scanf("%d%d",&l,&r);36         if(r>=minr[l])Ans[i]=1;37     }38     for(int i=1;i<=q;++i)printf("%d",Ans[i]);39     return 0;40 }
         
        
       
      

C.

考虑下方的点基本上是不太行的

所以应该是上方的那些点

模仿凸包的过程，判断改成判是否在抛物线里就行了

1 #include
      
        2 #define vec point 3 #define maxn 200005 4 #define pdd pair
       
         5 #define mp(a,b) make_pair(a,b) 6 using namespace std; 7 const double eps=1e-7; 8 int n; 9 struct point10 {11     double x,y;12     point(double x=0,double y=0):x(x),y(y){}13 }a[maxn],p[maxn],ch[maxn];14 bool operator < (point A,point B)15 {16     if(A.x==B.x)return A.y
        
         -eps)return 1;29     return 0;30 }31 int main()32 {33     scanf("%d",&n);34     for(int i=1;i<=n;++i)scanf("%lf%lf",&a[i].x,&a[i].y);35     sort(a+1,a+n+1);36     int cnt=0;37     for(int i=1;i
         
          eps)p[++cnt]=a[i];38     p[++cnt]=a[n];39     int top=0;40     for(int i=cnt;i;i--)41     {42         while(top>1&&in(p[i],getu(ch[top],ch[top-1])))top--;43         ch[++top]=p[i];44     }45     printf("%d\n",top-1);46     return 0;47 }