开学了，状态很差，没有考好。

T1是水题，话说我还非得打个对拍真是.......

直接二分就好了

 

1 #include
      
        2 #define int long long 3 using namespace std; 4 int n,d,a,b; 5 int work(int x) 6 { 7     if(a+(x*d)<=b+((n-1)-x)*d)return 1; 8     return 0; 9 }10 int work2(int x)11 {12     if(a+((n-1-x)*d)<=b+x*d)return 1;13 }14 signed main()15 {16     //freopen("text.in","r",stdin);17     //freopen("a.out","w",stdout);18     scanf("%lld%lld%lld%lld",&n,&d,&a,&b);19     if(n==1)20     {21        if(a!=b)printf("0\n");22        else printf("%lld\n",a);23        return 0;24     }25     int maxn=0;26     int l=0;int r=n-1;27     while(l+1
       
        >1;30           if(work(mid))l=mid;31           else r=mid;32     }33     if(work(r))34     {35        maxn=a+(r*d);36     }37     else if(work(l))maxn=a+(l*d);38     swap(a,b);39     l=0;r=n-1;40     while(l+1
        
         >1;43           if(work(mid))l=mid;44           else r=mid;45     }46     if(work(r))47     {48        maxn=max(a+(r*d),maxn);49     }50     else if(work(l))maxn=max(a+(l*d),maxn);   51     printf("%lld\n",maxn);52 }53 /*54 1 3 1 255 */
        
       
      

 

 

T2

以后绝对不用线段树查前趋

然后我们考虑用单调队列查前趋最大

正着扫一边，做单调下降序列

倒着扫一边，做单调不上升序列

这是因为会出现重复的情况，

例如a[1]=4,a[2]=2,a[3]=1,a[4]=2,a[5]=4;

当我们算位置2和4时肯定会把1-5算两次，

既然这样我们不妨把一个区间弄成左开右闭

这样我们相当于以2为中点，1和4为两侧的答案+以4为中点，1-5为两侧的答案，这样保证在算2时不会出现跨过4的区间所以正确

然后就没了，记得离散化

1 #include
      
        2 #define int long long 3 #define MAXN 210000 4 #define inf 0x7fffffff 5 using namespace std; 6 int yuan[MAXN],b[MAXN]; 7 int tot,n,m,kx; 8 int dp[MAXN];int end; 9 struct node{
    int id,a;}e[MAXN];10 int l[MAXN],r[MAXN];char orz[MAXN];11 int get_sum(int l,int head,int last,int r)12 {13     int anss=0;14     int l_len=head-l;int r_len=r-last;15     //printf("l_len=%lld r_len=%lld\n",l_len,r_len);16     anss+=l_len*r_len;17     anss+=(last-head+1)*r_len;18     anss+=(last-head+1)*l_len;19     int len=last-head+1;20     anss+=(len*(len+1))/2;    21     return anss;22 }int sum_maxn[MAXN];23 signed main()24 {25     //freopen("text.in","r",stdin);26     //freopen("kkk.out","w",stdout);27     scanf("%lld%lld",&n,&m);    28     for(int i=1;i<=n;++i)29     {30         scanf("%lld",&yuan[i]);e[i].a=yuan[i],e[i].id=i;31     }    32     tot=n;33     for(int i=1;i<=m;++i)34     {35         cin>>orz[i];36         scanf("%lld",&b[i]);37         yuan[++tot]=b[i];38     }39     sort(yuan+1,yuan+tot+1);40     kx=unique(yuan+1,yuan+tot+1)-yuan-1;41     for(int i=1;i<=n;++i)42     {43         e[i].a=lower_bound(yuan+1,yuan+kx+1,e[i].a)-yuan;44     }45     for(int i=1;i<=m;++i)46     {47         b[i]=lower_bound(yuan+1,yuan+kx+1,b[i])-yuan;48     }49     dp[0]=0;e[0].a=inf;end=0;50     for(int i=1;i<=n;++i)51     {52        while(e[i].a>=e[dp[end]].a)53        {54             end--;55        }56        l[i]=dp[end]+1;57        dp[++end]=e[i].id;58     }59     dp[0]=n+1;e[n+1].a=inf;end=0;60     for(int i=n;i>=1;--i)61     {62        while(e[i].a>e[dp[end]].a)63        {64             end--;65        }66        r[i]=dp[end]-1;67        dp[++end]=e[i].id;68     }69     for(int i=1;i<=n;++i)70     {71        sum_maxn[e[i].a]+=get_sum(l[i],i,i,r[i]);72     }73     for(int i=2;i<=kx;++i)sum_maxn[i]+=sum_maxn[i-1];74     for(int i=1;i<=m;++i)75     {76         if(orz[i]=='<')77         {78             printf("%lld\n",sum_maxn[b[i]-1]);79         }80         else if(orz[i]=='>')81         {82             printf("%lld\n",sum_maxn[kx]-sum_maxn[b[i]]);83         }84         else printf("%lld\n",sum_maxn[b[i]]-sum_maxn[b[i]-1]);85     }86 }
      

 弱弱的附上对拍

1 #include
      
        2 #define int long long 3 using namespace std; 4 signed main() 5 { 6     int c=0; 7     while(true) 8     { 9          c++;10          system("./pai");11          system("./ac");12          system("./kkk");    13          if(system("diff -b -B ac.out kkk.out"))14          {15             printf("%lld WA\n",c);16             return 0;17          }   18          printf("%lld AC\n",c);           19     }20 }21 /*22 g++ pai.cpp -o pai23 ./pai24 g++ ac.cpp -o ac25 ./ac26 g++ kkk.cpp -o kkk27 ./kkk28 g++ ran.cpp -o ran29 ./ran30 */
      

随机数据生成

1 #include
      
        2 #define int long long 3 using namespace std; 4 int random(int x) 5 { 6      return (long long)rand()*rand()%x; 7 } 8 void work() 9 {10      int x=random(10)+1;11      if(x%3==0)cout<<"> ";12      else if(x%4==0)cout<<"< ";13      else cout<<"= ";14 }15 signed main()16 {17     freopen("text.in","w",stdout);18     srand((unsigned)time(0));19     int n=random(10)+1;int m=10;20     printf("%lld %lld\n",n,m);21     for(int i=1;i<=n;++i)printf("%lld ",random(10)+1);22     cout<
      

 

T3

这是个打表题

于是我们设g[i]表示已经排好i-1个数，现在插入i时的方案

插入1，只需1步

插入2，需要1步将2提前，加上1的步数

插入3，需要将3提前，加上将1，2提前的步数

......

插入i需0步

这样g[i]=g[1-(i-1)]+1,然后我们可以看出这就是2^(i-1)

然后我们就可以把列出

ans=sigema(sigema(2^(j-1)))(1<=j<=i-1)(1<=i<=n)

然后根据数学知识就可以变成ans=ans+(2^(i-1))-1(1<=i<=n)

除以！i的逆元即可

 

1 #include
      
        2 #define int long long 3 #define MAXN 210000 4 using namespace std; 5 int f[MAXN],ni[MAXN]; 6 const int mod=1e9+7;int n; 7 int poww(int x,int y) 8 { 9     int ans=1;10     while(y)11     {12         if(y&1)ans=ans*x%mod;13         x=x*x%mod;14         y>>=1;15     }16     return ans%mod;17 }18 signed main()19 {20    scanf("%lld",&n);21    ni[0]=1;ni[1]=1;22    for(int i=2;i<=n;++i)ni[i]=(mod-mod/i)*ni[mod%i]%mod;23    for(int i=1;i<=n;++i)24    {25        f[i]=f[i-1]+(poww(2,i-1)-1+mod)%mod*ni[i]%mod;26    }27    printf("%lld\n",f[n]%mod);28 }