[关闭]
@Alpacadh 2019-02-16T17:01:12.000000Z 字数 7623 阅读 744

D、E、F题解

ACM

D - Tunnel Warfare

题意：

解题思路：

代码：

  1. #include<bits/stdc++.h>
  2. //#include<iostream>
  3. //#include<algorithm>
  4. //#include<cmath>
  5. //#include<cstring>
  6. //#include<stdio.h>
  7. //#include<cstdlib>
  8. //#include<cstdio>
  9. using namespace std;
  10. const int inf=0x3f3f3f3f;
  11. const int N=5e4+5;
  12. const double eps=1e-4;
  13. typedef long long ll;
  14. typedef pair<int,ll> pil;
  15. struct node
  16. {
  17.     int l,r,w,f;
  18.     int mi,ma;
  19.     int ls,rs,all;
  20. }tree[4*N+1];
  21. void build(int k,int ll,int rr)
  22. {
  23.     tree[k].l=ll,tree[k].r=rr;
  24.     tree[k].ls=tree[k].rs=tree[k].all=rr-ll+1;
  25.     if(tree[k].l==tree[k].r)
  26.     {
  27. //        scanf("%d",&tree[k].w);
  28.         return;
  29.     }
  30.     int m=(ll+rr)/2;
  31.     build(k*2,ll,m);
  32.     build(k*2+1,m+1,rr);
  33. //    tree[k].w=tree[k*2].w+tree[k*2+1].w;
  34. }
  35. void down(int k)
  36. {
  37.     tree[k*2].f+=tree[k].f;
  38.     tree[k*2+1].f+=tree[k].f;
  39.     tree[k*2].w+=tree[k].f*(tree[k*2].r-tree[k*2].l+1);
  40.     tree[k*2+1].w+=tree[k].f*(tree[k*2+1].r-tree[k*2+1].l+1);
  41.     tree[k].f=0;
  42. }
  43. void up(int k)
  44. {
  45. //    tree[k].w=tree[k*2].w+tree[k*2+1].w;
  46.     tree[k].ls=tree[2*k].ls;
  47.     if(tree[k].ls==tree[2*k].r-tree[2*k].l+1)
  48.         tree[k].ls+=tree[2*k+1].ls;
  49.     tree[k].rs=tree[2*k+1].rs;
  50.     if(tree[k].rs==tree[2*k+1].r-tree[2*k+1].l+1)
  51.         tree[k].rs+=tree[2*k].rs;
  52.     tree[k].all=max(tree[2*k].rs+tree[2*k+1].ls,max(tree[2*k].all,tree[2*k+1].all));
  53. }
  54. int ask_point(int k,int x)
  55. {
  56.     if(tree[k].l==tree[k].r||tree[k].all==0||tree[k].all==tree[k].r-tree[k].l+1)
  57.     {
  58.         return tree[k].all;
  59.     }
  60.     if(tree[k].f)
  61.         down(k);
  62.     int m=(tree[k].l+tree[k].r)/2;
  63.     if(x<=m)
  64.     {
  65.         if(x>=tree[2*k].r-tree[2*k].rs+1)
  66.             return tree[k*2].rs+tree[k*2+1].ls;
  67.         else
  68.             return ask_point(k*2,x);
  69.     }
  70.     else
  71.     {
  72.         if(x<=tree[2*k+1].l+tree[2*k+1].ls-1)
  73.             return tree[2*k+1].ls+tree[k*2].rs;
  74.         else
  75.             return ask_point(k*2+1,x);
  76.     }
  77. }
  78. void change_point(int k,int x,int y)
  79. {
  80.     if(tree[k].l==tree[k].r)
  81.     {
  82. //        tree[k].w+=y;
  83.         if(y==1)
  84.             tree[k].ls=tree[k].rs=tree[k].all=1;
  85.         else
  86.             tree[k].ls=tree[k].rs=tree[k].all=0;
  87.         return;
  88.     }
  89.     if(tree[k].f)
  90.         down(k);
  91.     int m=(tree[k].l+tree[k].r)/2;
  92.     if(x<=m)
  93.         change_point(k*2,x,y);
  94.     else
  95.         change_point(k*2+1,x,y);
  96.     up(k);
  97. }
  98. int ask_interval(int k,int a,int b)
  99. {
  100.     if(tree[k].l>=a&&tree[k].r<=b)
  101.     {
  102.         return tree[k].w;
  103.     }
  104.     if(tree[k].f)
  105.         down(k);
  106.     int m=(tree[k].l+tree[k].r)/2;
  107.     if(a<=m)
  108.         return ask_interval(k*2,a,b);
  109.     if(b>m)
  110.         return ask_interval(k*2+1,a,b);
  111.     up(k);
  112. }
  113. void change_interval(int k,int a,int b,int y)
  114. {
  115.     if(tree[k].l>=a&&tree[k].r<=b)
  116.     {
  117.         tree[k].w+=(tree[k].r-tree[k].l+1)*y;
  118.         tree[k].f+=y;
  119.         return;
  120.     }
  121.     if(tree[k].f)
  122.         down(k);
  123.     int m=(tree[k].l+tree[k].r)/2;
  124.     if(a<=m)
  125.         change_interval(k*2,a,b,y);
  126.     if(b>m)
  127.         change_interval(k*2+1,a,b,y);
  128.     up(k);
  129. }
  130. char s[10];
  131. int main()
  132. {
  133.     int n,m;
  134.     while(~scanf("%d%d",&n,&m))
  135.     {
  136.         stack<int>q;
  137.         memset(tree,0,sizeof(tree));
  138.         build(1,1,n);
  139.         while(m--)
  140.         {
  141.             scanf("%s",s);
  142.             if(s[0]=='D')
  143.             {
  144.                 int x;
  145.                 scanf("%d",&x);
  146.                 q.push(x);
  147.                 change_point(1,x,0);
  148.             }
  149.             else if(s[0]=='Q')
  150.             {
  151.                 int x;
  152.                 scanf("%d",&x);
  153.                 printf("%d\n",ask_point(1,x));
  154.             }
  155.             else
  156.             {
  157.                 int top=q.top();
  158.                 q.pop();
  159.                 change_point(1,top,1);
  160.             }
  161.         }
  162.     }
  163.     return 0;
  164. }

E - A Simple Problem with Integers

题意：

解题思路：

代码：

  1. //#include<bits/stdc++.h>
  2. #include<iostream>
  3. #include<algorithm>
  4. #include<cmath>
  5. #include<cstring>
  6. #include<stdio.h>
  7. #include<cstdlib>
  8. #include<cstdio>
  9. using namespace std;
  10. const int inf=0x3f3f3f3f;
  11. const int N=1e5+5;
  12. const double eps=1e-4;
  13. typedef long long ll;
  14. typedef pair<int,ll> pil;
  15. struct node
  16. {
  17.     int l,r;
  18.     ll w,f;
  19.     int mi,ma;
  20.     int ls,rs,all;
  21. }tree[4*N+1];
  22. void down(int k)
  23. {
  24.     tree[k*2].f+=tree[k].f;
  25.     tree[k*2+1].f+=tree[k].f;
  26.     tree[k*2].w+=tree[k].f*(tree[k*2].r-tree[k*2].l+1);
  27.     tree[k*2+1].w+=tree[k].f*(tree[k*2+1].r-tree[k*2+1].l+1);
  28.     tree[k].f=0;
  29. }
  30. void up(int k)
  31. {
  32.     tree[k].w=tree[k*2].w+tree[k*2+1].w;
  33. //    tree[k].ls=tree[2*k].ls;
  34. //    if(tree[k].ls==tree[2*k].r-tree[2*k].l+1)
  35. //        tree[k].ls+=tree[2*k+1].ls;
  36. //    tree[k].rs=tree[2*k+1].rs;
  37. //    if(tree[k].rs==tree[2*k+1].r-tree[2*k+1].l+1)
  38. //        tree[k].rs+=tree[2*k].rs;
  39. //    tree[k].all=max(tree[2*k].rs+tree[2*k+1].ls,max(tree[2*k].all,tree[2*k+1].all));
  40. }
  41. void build(int k,int ll,int rr)
  42. {
  43.     tree[k].l=ll,tree[k].r=rr;
  44. //    tree[k].ls=tree[k].rs=tree[k].all=rr-ll+1;
  45.     if(tree[k].l==tree[k].r)
  46.     {
  47.         tree[k].w=0;
  48. //        scanf("%d",&tree[k].w);
  49.         return;
  50.     }
  51.     int m=(ll+rr)/2;
  52.     build(k*2,ll,m);
  53.     build(k*2+1,m+1,rr);
  54.     up(k);
  55. }
  56. ll ask_point(int k,int x)
  57. {
  58.     if(tree[k].l==tree[k].r)
  59.     {
  60.         return tree[k].w;
  61.     }
  62.     if(tree[k].f)
  63.         down(k);
  64.     int m=(tree[k].l+tree[k].r)/2;
  65.     if(x<=m)
  66.     {
  67.         return ask_point(k*2,x);
  68.     }
  69.     else
  70.     {
  71.         return ask_point(k*2+1,x);
  72.     }
  73. }
  74. void change_point(int k,int x,int y)
  75. {
  76.     if(tree[k].l==tree[k].r)
  77.     {
  78.         tree[k].w+=y;
  79.         return;
  80.     }
  81.     if(tree[k].f)
  82.         down(k);
  83.     int m=(tree[k].l+tree[k].r)/2;
  84.     if(x<=m)
  85.         change_point(k*2,x,y);
  86.     else
  87.         change_point(k*2+1,x,y);
  88.     up(k);
  89. }
  90. ll ans;
  91. void ask_interval(int k,int a,int b)
  92. {
  93.     if(tree[k].l>=a&&tree[k].r<=b)
  94.     {
  95.         ans+=tree[k].w;
  96.         return;
  97.     }
  98.     if(tree[k].f)
  99.         down(k);
  100.     int m=(tree[k].l+tree[k].r)/2;
  101.     if(a<=m)
  102.          ask_interval(k*2,a,b);
  103.     if(b>m)
  104.          ask_interval(k*2+1,a,b);
  105. }
  106. void change_interval(int k,int a,int b,int y)
  107. {
  108.     if(tree[k].l>=a&&tree[k].r<=b)
  109.     {
  110.         tree[k].w+=(tree[k].r-tree[k].l+1)*y;
  111.         tree[k].f+=y;
  112.         return;
  113.     }
  114.     if(tree[k].f)
  115.         down(k);
  116.     int m=(tree[k].l+tree[k].r)/2;
  117.     if(a<=m)
  118.         change_interval(k*2,a,b,y);
  119.     if(b>m)
  120.         change_interval(k*2+1,a,b,y);
  121.     up(k);
  122. }
  123. char s[10];
  124. int main()
  125. {
  126.     int n,m;
  127.     scanf("%d%d",&n,&m);
  128.     build(1,1,n);
  129.     for(int i=1;i<=n;i++)
  130.     {
  131.         int a;
  132.         scanf("%d",&a);
  133.         change_point(1,i,a);
  134.     }
  135.     while(m--)
  136.     {
  137.         scanf("%s",s);
  138.         if(s[0]=='Q')
  139.         {
  140.             int a,b;
  141.             scanf("%d%d",&a,&b);
  142.             ans=0;
  143.             ask_interval(1,a,b);
  144.             printf("%lld\n",ans);
  145.         }
  146.         else
  147.         {
  148.             int a,b,c;
  149.             scanf("%d%d%d",&a,&b,&c);
  150.             change_interval(1,a,b,c);
  151.         }
  152.     }
  153.     return 0;
  154. }

F - Enemy is weak

题意：

解题思路：

代码：

  1. #include<bits/stdc++.h>
  2. //#include<iostream>
  3. //#include<algorithm>
  4. //#include<cmath>
  5. //#include<cstring>
  6. //#include<stdio.h>
  7. //#include<cstdlib>
  8. //#include<cstdio>
  9. using namespace std;
  10. const int inf=0x3f3f3f3f;
  11. const int N=1e6+5;
  12. const double eps=1e-4;
  13. typedef long long ll;
  14. typedef pair<int,ll> pil;
  15. struct node
  16. {
  17.     int l,r;
  18.     ll w,f;
  19.     int mi,ma;
  20.     int ls,rs,all;
  21. }tree[4*N+1];
  22. void down(int k)
  23. {
  24.     tree[k*2].f+=tree[k].f;
  25.     tree[k*2+1].f+=tree[k].f;
  26.     tree[k*2].w+=tree[k].f*(tree[k*2].r-tree[k*2].l+1);
  27.     tree[k*2+1].w+=tree[k].f*(tree[k*2+1].r-tree[k*2+1].l+1);
  28.     tree[k].f=0;
  29. }
  30. void up(int k)
  31. {
  32.     tree[k].w=tree[k*2].w+tree[k*2+1].w;
  33. //    tree[k].ls=tree[2*k].ls;
  34. //    if(tree[k].ls==tree[2*k].r-tree[2*k].l+1)
  35. //        tree[k].ls+=tree[2*k+1].ls;
  36. //    tree[k].rs=tree[2*k+1].rs;
  37. //    if(tree[k].rs==tree[2*k+1].r-tree[2*k+1].l+1)
  38. //        tree[k].rs+=tree[2*k].rs;
  39. //    tree[k].all=max(tree[2*k].rs+tree[2*k+1].ls,max(tree[2*k].all,tree[2*k+1].all));
  40. }
  41. void build(int k,int ll,int rr)
  42. {
  43.     tree[k].l=ll,tree[k].r=rr;
  44. //    tree[k].ls=tree[k].rs=tree[k].all=rr-ll+1;
  45.     if(tree[k].l==tree[k].r)
  46.     {
  47.         tree[k].w=0;
  48. //        scanf("%d",&tree[k].w);
  49.         return;
  50.     }
  51.     int m=(ll+rr)/2;
  52.     build(k*2,ll,m);
  53.     build(k*2+1,m+1,rr);
  54.     up(k);
  55. }
  56. ll ask_point(int k,int x)
  57. {
  58.     if(tree[k].l==tree[k].r)
  59.     {
  60.         return tree[k].w;
  61.     }
  62.     if(tree[k].f)
  63.         down(k);
  64.     int m=(tree[k].l+tree[k].r)/2;
  65.     if(x<=m)
  66.     {
  67.         return ask_point(k*2,x);
  68.     }
  69.     else
  70.     {
  71.         return ask_point(k*2+1,x);
  72.     }
  73. }
  74. void change_point(int k,int x,int y)
  75. {
  76.     if(tree[k].l==tree[k].r)
  77.     {
  78.         tree[k].w+=y;
  79.         return;
  80.     }
  81.     if(tree[k].f)
  82.         down(k);
  83.     int m=(tree[k].l+tree[k].r)/2;
  84.     if(x<=m)
  85.         change_point(k*2,x,y);
  86.     else
  87.         change_point(k*2+1,x,y);
  88.     up(k);
  89. }
  90. ll ans;
  91. void ask_interval(int k,int a,int b)
  92. {
  93.     if(tree[k].l>=a&&tree[k].r<=b)
  94.     {
  95.         ans+=tree[k].w;
  96.         return;
  97.     }
  98.     if(tree[k].f)
  99.         down(k);
  100.     int m=(tree[k].l+tree[k].r)/2;
  101.     if(a<=m)
  102.          ask_interval(k*2,a,b);
  103.     if(b>m)
  104.          ask_interval(k*2+1,a,b);
  105. }
  106. void change_interval(int k,int a,int b,int y)
  107. {
  108.     if(tree[k].l>=a&&tree[k].r<=b)
  109.     {
  110.         tree[k].w+=(tree[k].r-tree[k].l+1)*y;
  111.         tree[k].f+=y;
  112.         return;
  113.     }
  114.     if(tree[k].f)
  115.         down(k);
  116.     int m=(tree[k].l+tree[k].r)/2;
  117.     if(a<=m)
  118.         change_interval(k*2,a,b,y);
  119.     if(b>m)
  120.         change_interval(k*2+1,a,b,y);
  121.     up(k);
  122. }
  123. int a[N],b[N];
  124. ll ansl[N],ansr[N];
  125. int main()
  126. {
  127.     int n;
  128.     scanf("%d",&n);
  129.     for(int i=1;i<=n;i++)
  130.     {
  131.         scanf("%d",&a[i]);
  132.         b[i]=a[i];
  133.     }
  134.     sort(b+1,b+1+n);
  135.     int cnt=unique(b+1,b+1+n)-(b+1);//离散化操作
  136.     for(int i=1;i<=n;i++)
  137.         a[i]=lower_bound(b+1,b+1+cnt,a[i])-b;//离散化操作
  138.     build(1,1,n);
  139.     for(int i=n;i>=1;i--)
  140.     {
  141.         ans=0;
  142.         ask_interval(1,1,a[i]);
  143.         ansr[i]=ans;
  144.         change_point(1,a[i],1);
  145.     }
  146.     for(int i=1;i<=n;i++)
  147.     {
  148.         ansl[i]=i-a[i]+ansr[i];
  149.     }
  150.     ll res=0;
  151.     for(int i=1;i<=n;i++)
  152.         res+=ansl[i]*ansr[i];
  153.     printf("%lld\n",res);
  154.     return 0;
  155. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注