Day 2

上午的听课，哎~昏昏欲睡好吧。。

一、扫描线

知识点：

由于多边形千变万化，要想填充多边形内部的所有像素，需要找到一种合适的规则，能够沿着一个方向，一个像素不漏地把多边形内部填满，同时不污染多边形外部。于是我们发明了一条水平方向的扫描线，它从y=0开始，判断与多边形的交点，这些交点把扫描线分成了若干段，我们需要判断哪些段在多边形内部，哪些段在多边形外部，然后把内部的部分着色，完成后，令y=y+1，即扫描线上移一格，重复之前的操作，直到扫描线不再与多边形的任何部分相交。

例题（poj 1151）：

 

 

代码实现：

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 using namespace std; 7 const int N=110; 8 double w[N<<1]; 9 double x,y,dx,dy,ans;10 int n,res=0,js;11 12 struct edge {13     double l,r,h;14     int f;15 }e[N<<1];16 17 struct node {18     int l,r,s;19     double lc;20 }q[N<<3];21 22 inline bool cmp(edge a,edge b) {23     return a.h
           
            >1;30 build(i<<1,l,mid);31 build(i<<1|1,mid+1,r);32 }33 34 inline void push_up(int i) {35 if(q[i].s) q[i].lc=w[q[i].r+1]-w[q[i].l]; 36 else if(q[i].l==q[i].r) q[i].lc=0;37 else q[i].lc=q[i<<1].lc+q[i<<1|1].lc;38 }39 40 void up_date(int i,int l,int r,int v) {41 if(q[i].l==l && q[i].r==r) {42 q[i].s+=v;43 push_up(i);44 return;45 }46 int mid=(q[i].l+q[i].r)>>1;47 if(r<=mid) up_date(i<<1,l,r,v);48 else if(l>mid) up_date(i<<1|1,l,r,v);49 else up_date(i<<1,l,mid,v),up_date(i<<1|1,mid+1,r,v);50 push_up(i);51 }52 53 inline void IU() {54 e[js]=(edge) {x,dx,y,1};55 w[js]=x;56 e[js+1]=(edge){x,dx,dy,-1};57 w[js+1]=dx;58 }59 60 int main() {61 while (scanf("%d",&n)==1 && n) {62 js=0;63 for(int i=0;i
           
          
         
        
       
      

 

二、线段树（大全）

知识点：

线段树是一种，与相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。对于线段树中的每一个非[a,b]，它的左儿子表示的区间为[a,(a+b)/2]，右儿子表示的区间为[(a+b)/2+1,b]。因此线段树是，最后的子节点数目为N，即整个线段区间的长度。使用线段树可以快速的查找某一个节点在若干条线段中出现的次数，时间复杂度为O(logN)。而未优化的为2N，因此有时需要离散化让空间压缩。线段树至少支持下列操作:

1.Insert(t,x):将包含在区间 int 的元素 x 插入到树t中;

2.Delete(t,x):从线段树 t 中删除元素 x;

3.Search(t,x):返回一个指向树 t 中元素 x 的指针。

线段树代码实现：

1 #include
      
        2 #include
       
         3 using namespace std; 4 const int N=100000; 5 int sum[N<<2],a[N+1]; 6 int n,m,k,L,R; 7  8 inline int read() { 9     int n=0,f=1;char ch=getchar();10     while (ch<'0' || ch>'9') {
    if(ch=='-') f=-1;ch=getchar();}11     while (ch<='9' && ch>='0') {n=(n<<3)+(n<<1)+ch-'0';ch=getchar();}12     return n*f;13 }14 15 inline void push_up(int rt) {16     sum[rt]=sum[rt<<1]+sum[rt<<1|1];17 }18 19 inline void build(int l,int r,int rt) {20     if(l==r) {21         sum[rt]=a[l];22         return ;23     }24     int m=(l+r)>>1;25     build(l,m,rt<<1),build(m+1,r,rt<<1|1);26     push_up(rt);27 }28 29 inline int query(int L,int R,int l,int r,int rt) {30     if(L<=l&&r<=R) return sum[rt];31     int s=0;32     int m=(l+r)>>1;33     if(L<=m) s+=query(L,R,l,m,rt<<1);34     if(R>m) s+=query(L,R,m+1,r,rt<<1|1);35     return s;36 }37 38 inline void up_date(int L,int C,int l,int r,int rt) {39     if(l==r) { 40         sum[rt]+=C;41         return;42     }43     int m=(l+r)>>1;44     if(L<=m) up_date(L,C,l,m,rt<<1);45     else up_date(L,C,m+1,r,rt<<1|1); 46     push_up(rt);47 }48 49 int main() {50     n=read();51     for(int i=1;i<=n;++i) a[i]=read();52     build(1,n,1);53     m=read();54     for(int i=0;i
       
      

 

线段树（区间加及求和）代码实现：

1 #include
      
        2 #include
       
         3 #define N 1000001 4 #define ll long long 5 using namespace std; 6 ll a[N],ans[N<<2],t[N<<2]; 7 ll bz,b,c,d,e,f,n,m; 8  9 inline ll read() {10     ll n=0,f=1;char ch=getchar();11     while (ch<'0'||ch>'9') {
    if(ch=='-') f=-1;ch=getchar();}12     while (ch<='9'&&ch>='0') {n=n*10+ch-'0';ch=getchar();}13     return n*f;14 } 15 16 inline void pushup_(ll i) {17     ans[i]=ans[i<<1]+ans[i<<1|1];18 }19 20 inline void build(ll i,ll l,ll r) {21     t[i]=0;22     if(l==r) {23         ans[i]=a[l];24         return ;25     }26     ll mid=(l+r)>>1;27     build(i<<1,l,mid);28     build(i<<1|1,mid+1,r);29     pushup_(i);30 }31 32 inline void work_(ll i,ll l,ll r,ll k) {33     t[i]=t[i]+k;34     ans[i]=ans[i]+k*(r-l+1);35 }36 37 inline void push_down(ll i,ll l,ll r) {38     ll mid=(l+r)>>1;39     work_(i<<1,l,mid,t[i]);40     work_(i<<1|1,mid+1,r,t[i]);41     t[i]=0;42 }43 44 inline void _work(ll a,ll b,ll l,ll r,ll i,ll k) {45     if(a<=l&&r<=b) {46         ans[i]+=k*(r-l+1);47         t[i]+=k;48         return ;49     }50     push_down(i,l,r);51     ll mid=(l+r)>>1;52     if(a<=mid) _work(a,b,l,mid,i<<1,k);53     if(b>mid) _work(a,b,mid+1,r,i<<1|1,k);54     pushup_(i);55 }56 57 inline ll query(ll a,ll b,ll l,ll r,ll i) {58     ll s=0;59     if(a<=l&&r<=b) return ans[i];60     ll mid=(l+r)>>1;61     push_down(i,l,r);62     if(a<=mid) s+=query(a,b,l,mid,i<<1);63     if(b>mid) s+=query(a,b,mid+1,r,i<<1|1);64     return s;65 }66 67 int main() {68     n=read(),m=read();69     for(ll i=1;i<=n;++i) a[i]=read();70     build(1,1,n);71     while(m--) {72         bz=read();73         if(bz==1) {74             b=read(),c=read(),d=read();75             _work(b,c,1,n,1,d);76             continue;77         }78         if(bz==2) {79             e=read(),f=read();80             printf("%lld\n",query(e,f,1,n,1));81             continue;82         }83     }84     return 0;85 }
       
      

 

线段树（区间修改及询问）代码实现：

1 #include
      
        2 #include
       
         3 using namespace std; 4 typedef long long ll; 5 const int N=1e6+10; 6 ll t[N],bz[N],dz[N],L[N],R[N]; 7 int n,m,f,x,y; 8 ll add; 9 10 inline int read() {11     int n=0,f=1;char ch=getchar();12     while (ch<'0'||ch>'9') {
    if(ch=='-') f=-1;ch=getchar();}13     while (ch<='9'&&ch>='0') {n=n*10+ch-'0';ch=getchar();}14     return n*f;15 } 16 17 inline ll readx() {18     ll n=0,f=1;char ch=getchar();19     while (ch<'0'||ch>'9') {
    if(ch=='-') f=-1;ch=getchar();}20     while (ch<='9'&&ch>='0') {n=n*10+ch-'0';ch=getchar();}21     return n*f;22 } 23 24 inline void _work(int i,int l,int r) {25     L[i]=l,R[i]=r;26     int mid=(l+r)>>1;27     if(l==r) {28         t[i]=dz[l];29         return;30     }31     _work(i<<1,l,mid),_work(i<<1|1,mid+1,r);32     t[i]=t[i<<1]+t[i<<1|1];33 }34 35 inline void down_(int i) {36     if(bz[i]) {37         int mid=(L[i]+R[i])>>1;38         t[i<<1]+=(mid-L[i]+1)*bz[i];39         t[i<<1|1]+=(R[i]-mid)*bz[i];40         bz[i<<1]+=bz[i];41         bz[i<<1|1]+=bz[i];42         bz[i]=0;43     }44 }45 46 inline void work_(int i,int l,int r,ll add) {47     if(L[i]>=l && R[i]<=r) {48         t[i]+=(R[i]-L[i]+1)*add;49         bz[i]+=add;50         return;51     }52     if(L[i]>r || R[i]
        
         =l && R[i]<=r) return t[i];60     if(L[i]>r || R[i]
        
       
      

 

线段树（区间加乘及求和）代码实现：

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #include
           
             7 #define ll long long int 8 using namespace std; 9 int const N=4e5+10; 10 11 struct Tre { 12 ll sum, v, bz, l, r; 13 }e[N]; 14 15 ll n,m,mod,L,R,val,bz; 16 ll t[N]; 17 18 inline ll read() { 19 ll n=0,f=1;char ch=getchar(); 20 while (ch<'0'||ch>'9') { if(ch=='-') f=-1;ch=getchar();} 21 while (ch<='9'&&ch>='0') {n=n*10+ch-'0';ch=getchar();} 22 return n*f; 23 } 24 25 inline void push_up(ll i) { 26 e[i].sum=(e[i<<1].sum+e[i<<1|1].sum)%mod; 27 } 28 29 inline void build(ll l, ll r, ll i) { 30 e[i].l=l,e[i].r=r,e[i].bz=1; 31 if(l==r) { 32 e[i].sum=t[l]%mod; 33 return; 34 } 35 ll mid=(l+r)>>1; 36 build(l,mid,i<<1),build(mid+1,r,i<<1|1); 37 push_up(i); 38 } 39 40 inline void pushdown(ll i) { 41 if(e[i].bz!=1) { 42 e[i<<1].v*=e[i].bz; e[i<<1|1].v*=e[i].bz; 43 e[i<<1].bz*=e[i].bz; e[i<<1|1].bz*=e[i].bz; 44 e[i<<1].sum*=e[i].bz; e[i<<1|1].sum*=e[i].bz; 45 e[i<<1].v%=mod; e[i<<1|1].v%=mod; 46 e[i<<1].bz%=mod; e[i<<1|1].bz%=mod; 47 e[i<<1].sum%=mod; e[i<<1|1].sum%=mod; 48 e[i].bz=1; 49 } 50 if(e[i].v) { 51 e[i<<1].v+=e[i].v; e[i<<1|1].v+=e[i].v; 52 e[i<<1].sum+=(e[i<<1].r-e[i<<1].l+1)*e[i].v; 53 e[i<<1|1].sum+=(e[i<<1|1].r-e[i<<1|1].l+1)*e[i].v; 54 e[i<<1].v%=mod; e[i<<1|1].v%=mod; 55 e[i<<1].sum%=mod; e[i<<1|1].sum%=mod; 56 e[i].v=0; 57 } 58 } 59 60 inline void work_(ll i) { 61 if(e[i].l>=L && e[i].r<=R) { 62 e[i].bz*=val%mod; e[i].bz%=mod; 63 e[i].v*=val%mod; e[i].v%=mod; 64 e[i].sum*=val%mod; e[i].sum%=mod; 65 return; 66 } 67 pushdown(i); 68 ll mid=(e[i].l+e[i].r)>>1; 69 if(L<=mid) work_(i<<1); 70 if(R>mid) work_(i<<1|1); 71 push_up(i); 72 } 73 74 inline void _work(ll i) { 75 if(e[i].l>=L && e[i].r<=R) { 76 e[i].sum+=((e[i].r-e[i].l+1)*val)%mod; 77 e[i].sum%=mod; e[i].v+=val%mod; 78 e[i].v%=mod; 79 return; 80 } 81 pushdown(i); 82 ll mid=(e[i].l+e[i].r)>>1; 83 if(L<=mid) _work(i<<1); 84 if(R>mid) _work(i<<1|1); 85 push_up(i); 86 } 87 88 inline ll query(ll i) { 89 if(e[i].l>=L && e[i].r<=R) return e[i].sum%mod; 90 pushdown(i); 91 ll mid=(e[i].l+e[i].r)>>1, ret=0; 92 if(L<=mid) ret=(ret+query(i<<1)%mod)%mod; 93 if(R>mid) ret=(ret+query(i<<1|1)%mod)%mod; 94 push_up(i); 95 return ret%mod; 96 } 97 98 int main() { 99 n=read(),m=read(),mod=read();100 for(int i=1;i<=n;++i) t[i]=read();101 build(1,n,1);102 for(int i=1;i<=m;++i) {103 bz=read();104 if(bz==1) {105 L=read(),R=read(),val=read();106 work_(1);107 } else if(bz==2) {108 L=read(),R=read(),val=read();109 _work(1);110 } else {111 L=read(),R=read();112 printf("%d\n", query(1));113 }114 }115 return 0;116 }
           
          
         
        
       
      

 

线段树（区间修改及询问，单点修改及询问） 代码实现：

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 #define ll long long int 8 using namespace std; 9 int n,m,opt,b,c,x;10 const int N=6e5+10;11 12 struct note {13 int l,r,s;14 } t[N]; 15 16 inline int read() {17 int n=0,f=1;char ch=getchar();18 while (ch<'0' || ch>'9') { if(ch=='-') f=-1;ch=getchar();}19 while (ch<='9' && ch>='0') {n=(n<<3)+(n<<1)+ch-'0';ch=getchar();}20 return n*f;21 }22 //建树 23 inline void build(int k,int l,int r) {24 int lc=k<<1,rc=k<<1|1;25 t[k].l=l,t[k].r=r;26 int mid=(l+r)/2;27 if(l==r) {28 t[k].s=read();29 return;30 }31 build(lc,l,mid),build(rc,mid+1,r);32 t[k].s=t[lc].s+t[rc].s;33 }34 //单点修改35 inline void _change(int k,int p,int v) {36 int lc=k<<1,rc=k<<1|1;37 int l=t[k].l,r=t[k].r;38 if(l==r) {39 t[k].s+=v;40 return ;41 }42 int mid=(l+r)>>1;43 if(p<=mid) _change(lc,p,v);44 else _change(rc,p,v);45 t[k].s=t[lc].s+t[rc].s;46 }47 //区间修改48 inline void change_(int k,int l,int r,int v) {49 int lc=k<<1,rc=k<<1|1;50 if(t[k].l==t[k].r) {51 t[k].s+=v;52 return ;53 }54 int mid=(t[k].l+t[k].r)>>1;55 if(l<=mid) change_(lc,l,min(r,mid),v);56 if(r>mid) change_(rc,max(l,mid+1),r,v);57 t[k].s=t[lc].s+t[rc].s;58 }59 //单点查询60 inline int _query(int k,int p) { 61 int lc=k<<1,rc=k<<1|1;62 int l=t[k].l,r=t[k].r;63 if(l==r) return t[k].s;64 int mid=(l+r)>>1;65 if(p<=mid) return _query(lc,p);66 else return _query(rc,p);67 }68 //区间查询69 inline int query_(int k,int l,int r) { 70 int lc=k<<1,rc=k<<1|1;71 if(t[k].l==l&&t[k].r==r) return t[k].s;72 int mid=(t[k].l+t[k].r)>>1,ans=0;73 if(l<=mid) ans+=query_(lc,l,min(r,mid));74 if(r>mid) ans+=query_(rc,max(l,mid+1),r);75 return ans;76 }77 78 int main() {79 n=read();80 build(1,1,n);81 m=read();82 for(int i=1;i<=m;++i) {83 opt=read();84 if(opt==1) {85 b=read(),c=read(),x=read();86 change_(1,b,c,x);87 }88 if(opt==2) {89 b=read();90 printf("%d\n",_query(1,b));91 }92 if(opt==3) {lue...}93 if(opt==4) {lue...}94 }95 return 0;96 }