ZigZagK的博客
[扫描线]Codeforces853C【Boredom】题解
[扫描线]Codeforces853C【Boredom】题解
2020年9月29日 17:45
查看标签

题目概述

CF853C

解题报告

直接求很麻烦,我们求不满足的个数。对于询问的矩形 $A$ ,我们划分出八个区域:

  • 1
  • 2
  • 3
  • 4
  • 5
| 0 | 1 | 2 | ------------- | 3 | A | 4 | ------------- | 5 | 6 | 7 |

这八个区域中不跨越 $A$ 的两个区域中的点组合就是不满足的。

所以对于每个询问我们要求出八个区域中点的个数,由于询问离线,我们用扫描线就行了。

示例程序

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
#include<cstdio> #include<cctype> #include<algorithm> using namespace std; typedef long long LL; const int maxn=200000,maxq=200000,maxt=maxq*16; int n,Q,m,a[maxn+5],f[maxq+5][8],c[maxn+5]; struct data {int x,L,R,f;int *F;} q[maxt+5]; #define EOLN(x) ((x)==10 || (x)==13 || (x)==EOF) inline char readc(){ static char buf[100000],*l=buf,*r=buf; return l==r && (r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++; } template<typename T> int readi(T &x){ T tot=0;char ch=readc(),lst='+'; while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();} while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc(); lst=='-'?x=-tot:x=tot;return EOLN(ch); } void Add(int A,int B,int C,int D,int *F){ if (A<1 || B>n || C<1 || D>n || A>C || B>D) return; if (A>1) q[++m]=(data){A-1,B,D,-1,F}; q[++m]=(data){C,B,D,1,F}; } inline bool cmp(const data &a,const data &b) {return a.x<b.x;} void Insert(int x,int y) {for (int i=x;i<=n;i+=i&-i) c[i]+=y;} int Sum(int x) {int sum=0;for (int i=x;i;i-=i&-i) sum+=c[i];return sum;} #define C2(n) ((LL)(n)*((n)-1)>>1) #define Count(a,b,c) ((LL)(a)*(b)+(LL)(a)*(c)+(LL)(b)*(c)) int main(){ freopen("853C.in","r",stdin);freopen("853C.out","w",stdout); readi(n);readi(Q);for (int i=1;i<=n;i++) readi(a[i]); for (int i=1;i<=Q;i++){ int A,B,C,D;readi(A);readi(B);readi(C);readi(D); Add(1,1,A-1,B-1,&f[i][0]);Add(1,B,A-1,D,&f[i][1]); Add(1,D+1,A-1,n,&f[i][2]);Add(A,1,C,B-1,&f[i][3]); Add(A,D+1,C,n,&f[i][4]);Add(C+1,1,n,B-1,&f[i][5]); Add(C+1,B,n,D,&f[i][6]);Add(C+1,D+1,n,n,&f[i][7]); } sort(q+1,q+1+m,cmp); for (int i=1,j=1;i<=n;i++) for (Insert(a[i],1);j<=m && q[j].x==i;j++) *q[j].F+=q[j].f*(Sum(q[j].R)-Sum(q[j].L-1)); for (int i=1;i<=Q;i++){ LL ans=C2(n); for (int j=0;j<8;j++) ans-=C2(f[i][j]); ans-=Count(f[i][0],f[i][1],f[i][2]); ans-=Count(f[i][5],f[i][6],f[i][7]); ans-=Count(f[i][0],f[i][3],f[i][5]); ans-=Count(f[i][2],f[i][4],f[i][7]); printf("%lld\n",ans); } return 0; }
版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!
本文写于 1562 天前,最后更新于 1562 天前。
部分信息可能已经过时,博主也可能已经无法对其内容进行解答。
OK
  1. 1 感情の摩天楼 ~ Cosmic Mind 上海アリス幻樂団
  2. 2 秘匿されたフォーシーズンズ 上海アリス幻樂団
  3. 3 Ideal and the Real 小西利樹
  4. 4 Undertale Toby Fox
  5. 5 First Steps Lena Raine
  6. 6 City of Tears Christopher Larkin
  7. 7 The truth that you leave Pianoboy高至豪
  8. 8 Blaze A Trail October
  9. 9 Tower Of Heaven (You Are Slaves) Feint
感情の摩天楼 ~ Cosmic Mind - 上海アリス幻樂団
00:00 / 00:00
An audio error has occurred, player will skip forward in 2 seconds.

作曲 : ZUN

纯音乐,请欣赏