1877: 蛤瑋打掃教室

Time Limit: 2 Sec??Memory Limit: 128 MB
Submit: 332??Solved: 71

SubmitStatusWeb Board

Description

?

?

現在知道一共有n個機房,算上蛤瑋一共有m個隊員,教練做了m個簽,每個簽上寫著兩個數L,R(L<=R),抽到的人要把[L,R]的教室全部打掃一遍.由于蛤瑋是隊長而且他很懶,他通過某種交易提前知道了所有m個簽上面寫的是什么,而且通過某種魔法可以控制自己抽到哪個簽.一個教室被打掃一次就干凈了,所以蛤瑋想知道自己抽哪些簽可以不用打掃教室而且不會被教練發現,即他抽到的區間全都會被別人打掃一遍.

?

?

蛤瑋被教練叫去打掃機房,集訓隊有很多機房,也有很多隊員,現在他們要用抽簽的方式決定誰打掃哪間教室.

Input

第一行為一個整數T(1<=T<=20)，代表數據組數。每組數據第一行n,m(1<=n,m<=100000),接下來m行,每行兩個數L,R(1<=L<=R<=n).

?

Output

每組數據輸出一個k,表示多少個簽符合蛤瑋的要求,接下來一行輸出k個數,這些簽的編號,下標從1開始.

?

Sample Input

315 51 45 56 89 105 63 61 11 12 22 23 33 310 31 42 66 10

Sample Output

22 561 2 3 4 5 60

線段樹代碼：

#include<stdio.h> #include<string> #include<string.h> #include<iostream> #include<algorithm> using namespace std; const int maxn=100005; struct node {int left;//區間端點int right;int num_num;//當前區間被覆蓋次數 } Tree[maxn<<2]; //建樹,所需空間是標準的4倍 struct noden {int left_num;//區間端點int right_num; } num[maxn]; //接收數據 int flag[maxn];//存儲符合條件的區間序號 void Build(int root,int left,int right)//建樹，傳入根節點及根節點區間 {Tree[root].left=left;//記錄當前區間左右端點值Tree[root].right=right;Tree[root].num_num=0;//初始化當前區間被覆蓋數量if(left==right)//遞歸構造終止條件return;int mid=(left+right)>>1;//取中值Build(root<<1,left,mid);Build(root<<1|1,mid+1,right); } void Update(int root,int left,int right)//更新樹，傳入根節點及待更新區間 {if(Tree[root].left==left&&Tree[root].right==right){Tree[root].num_num++;return;//待更新區間與當前區間完全重合，則計數數據加1并終止更新}int mid=(Tree[root].left+Tree[root].right)>>1;//取中間值if(right<=mid)//待更新區間完全在當前區間左半部分Update(root<<1,left,right);else if(left>mid)//待更新區間完全在當前區間右半部分Update(root<<1|1,left,right);else//待更新區間橫跨當前區間{Update(root<<1,left,mid);//左右部分分別更新Update(root<<1|1,mid+1,right);} } int Query(int root,int left,int right)//查詢樹，傳入根節點及查詢區間，返回查詢區間計數num_num，有多個時，返回較小值 {if(Tree[root].left==left&&Tree[root].right==right)return Tree[root].num_num;//待查詢區間與當前區間完全重疊，直接返回計數數據num_numint mid=(Tree[root].left+Tree[root].right)>>1;//取中值if(right<=mid)//待查詢區間完全在當前區間左半部分return Query(root<<1,left,right);else if(left>mid)//待查詢區間完全在當前區間右半部分return Query(root<<1|1,left,right);else//待查詢區間橫跨當前區間左右兩部分return min(Query(root<<1,left,mid),Query(root<<1|1,mid+1,right)); } void Up(int root,int left,int right)//下沉計數數據num {if(left==right)return;Tree[root<<1].num_num+=Tree[root].num_num;Tree[root<<1|1].num_num+=Tree[root].num_num;int mid=(Tree[root].left+Tree[root].right)>>1;//取中值Up(root<<1,left,mid);//更新當前區間左半部分Up(root<<1|1,mid+1,right);//更新當前區間右半部分Tree[root].num_num=min(Tree[root<<1].num_num,Tree[root<<1|1].num_num);//更新當前區間對應計數數據num_num } int main() {int T;//T組數據scanf("%d",&T);while(T--){int n;//機房數量,也是根節點對應區間的右端點int m;//抽簽數量memset(num,0,sizeof(num));memset(flag,0,sizeof(flag));memset(Tree,0,sizeof(Tree));scanf("%d%d",&n,&m);Build(1,1,n);for(int i=1; i<=m; i++){scanf("%d%d",&num[i].left_num,&num[i].right_num);Update(1,num[i].left_num,num[i].right_num);//更新樹}Up(1,1,n);//下沉計數數據numint sum=0;//記錄區間數量for(int i=1; i<=m; i++)if(Query(1,num[i].left_num,num[i].right_num)>=2)flag[sum++]=i;//記錄區間序數和滿足條件的區間數量if(sum==0)printf("0\n");else{printf("%d\n%d",sum,flag[0]);for(int i=1; i<sum; i++)printf(" %d",flag[i]);printf("\n");}}return 0; }

另一個：

#include<iostream> #include<cstdio> #include<cstring> #include<queue> #include<vector> using namespace std; const int maxn=2e5+7; int a[maxn],b[maxn],c[maxn]; struct Node{int l,r;}p[maxn]; vector<int>ans; int main() {int T;scanf("%d",&T);while(T--){ans.clear();memset(a,0,sizeof(a));memset(c,0,sizeof(c));int n,m;scanf("%d%d",&n,&m);for(int i=0;i<m;i++){int x,y;scanf("%d%d",&x,&y);a[x]++,a[n+y]--;p[i].l=x,p[i].r=y;}int cnt=0;for(int i=1;i<=n;i++){cnt+=a[i];b[i]=cnt;cnt+=a[n+i];}for(int i=1;i<=n;i++){if(b[i]>1)c[i]=c[i-1]+1;else c[i]=c[i-1];}for(int i=0;i<m;i++){if(c[p[i].r]-c[p[i].l-1]==p[i].r-p[i].l+1)ans.push_back(i);}int len=ans.size();printf("%d\n",len);if(len){for(int i=0;i<len-1;i++)printf("%d ",ans[i]+1);printf("%d\n",ans[len-1]+1);}}return 0; }

?

總結

以上是生活随笔為你收集整理的蛤玮打扫教室（区间覆盖）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。